Optimized approach
The idea is simple. Initially, we put all the negative elements together, starting from index 0. Then we put two pointers at the start of negative and positive elements, and we keep on swapping alternate positions until we reach a point where either positive or negative elements get exhausted, and automatically extra positive or negative elements are put at the end. At last, all elements will be rearranged to occupy alternate positive and negative positions.
Steps of Algorithm
- Initialize a variable temp = -1, which will put all negative elements at the front.
- Start traversing the array arr[], and if at any point arr[i]<0, then make temp++, and swap(arr[temp], arr[i]).
- After positioning all the negative elements at the front, initilize two more variable pos = temp+1, neg = 0. Now these variable are located at start of negative and positive elements, and we will keep on swapping arr[pos] and arr[neg] until this condition is satisfied :: pos<size && neg<pos && arr[neg]<0.
Implementation in C++
// C++ program to rearrange postive and negative elements
#include<bits/stdc++.h>
using namespace std;
int main() {
vector < int > arr = {-1, 2, 1, 3, -1, -2, -3};
int n = arr.size();
// printing the array before rearrangement
cout << "Array before the rearrangement: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
// intiliazing the temp variable to bring negative elements at the front
int temp = -1;
// for loop to bring all the negative elements at the front of the array
for (int i = 0; i < n; i++) {
if (arr[i] < 0) swap(arr[i], arr[++temp]);
}
// intializing the two variable pos and neg,
int pos = temp + 1, neg = 0;
//now we will swap positive and negative elements
while (pos < n && arr[neg] < 0 && pos > neg) {
swap(arr[pos], arr[neg]);
pos++;
neg += 2;
}
cout << "Printing the array after rearrangement: ";
for (int i = 0; i < n; i++) cout << arr[i] << " ";
cout << endl;
}
Output:
Array before the rearrangement: -1 2 1 3 -1 -2 -3
Printing the array after rearrangement: 2 -1 1 -3 3 -2 -1
Implementation in Python
# python program to rearrange positive and negative elements
from operator import ne
arr = [-1,2,1,3,-1,-2,-3]
# printing the array before rearrangement
print("Array before the rearrangement: ")
print(arr)
# intiliazing the temp variable to bring negative elements at the front
temp = -1
n = len(arr)
for i in range (0, n):
if arr[i]<0:
temp = temp+1
arr[i],arr[temp] = arr[temp], arr[i]
#intializing the two variable pos and neg,
pos = temp+1
neg = 0
#now we will swap positive and negative elements
while(pos<n and arr[neg]<0 and neg<pos):
arr[pos], arr[neg] = arr[neg], arr[pos]
pos = pos+1
neg = neg+2
# printing the array before rearrangement
print("Array after the rearrangement: ")
print(arr)
Output:
Array before the rearrangement:
[-1, 2, 1, 3, -1, -2, -3]
Array after the rearrangement:
[2, -1, 1, -3, 3, -2, -1]
Complexity Analysis
Time Complexity: O(N)
We are traversing the arr[] only twice, so O(2*N) ~ O(N).
Space Complexity: O(1)
We are not using any temporary array, so therefore space complexity is O(1).
Check out this array problem - Merge 2 Sorted Arrays
Frequently Asked Questions
What is the greedy approach?
It is an algorithm to get the optimal solution for the problem. In this algorithm, we always choose the next best solution that seems optimal at that step. We build solutions piece by piece to reach the optimal solution.
Which sorting algorithm is used when we sort using STL?
The sorting algorithm used in STL sort() is IntroSort. Introsort is a hybrid sorting algorithm that uses three sorting algorithms to minimize the running time. These algorithms are quicksort, Heapsort, and Insertion Sort.
How many subsets are possible of an array of length N?
There are 2^N possible subsets of an array of length N.
Also Read - Strong number in c
Conclusion
In this article, we discussed a very interesting problem, in which we have to rearrange the positive and negative numbers such that they will occupy alternate positions, and all extra positive or negative elements will be put to an end.
We hope you understand the problem and solution properly. Now you can do more similar questions.
Recommended Problems -
Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enroll in our courses and refer to the mock test and problems available, interview puzzles, take a look at the interview experiences, and interview bundle for placement preparations.
Thank you for reading.
Until then, Keep Learning and Keep Coding.
305+ registered