1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Brute Force Approach
3.
Optimized approach
3.1.
Steps of Algorithm
3.2.
Implementation in C++
3.3.
Implementation in Python
3.4.
Complexity Analysis
4.
4.1.
What is the greedy approach?
4.2.
Which sorting algorithm is used when we sort using STL?
4.3.
How many subsets are possible of an array of length N?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Rearrange Positive and negative numbers in O(n) time and O(1) extra space

Introduction

This article will look at the Rearrangement of positive and negative numbers. Array-based questions are the most popular and vital in coding interviews and programming competitions. Let's understand the problem statement.

Problem Statement

The problem states that we are given an array of size N, containing both positive and negative numbers, and we need to rearrange the array such that all positive and negative numbers are at alternate positions. If there are extra positive or negative numbers, then put those extra numbers at the end of the array.

Let’s Discuss the sample example to understand the problem better.

Sample Examples

Input 1:

``arr[] = {-1,2,1,3,-1,-2,-3}``

Output 1:

``{2, -1, 1, -3, 3, -2, -1}``

Explanation:

``In the above example, we have rearranged all positive and negative numbers at alternate positions, and extra negative elements are put at the end.  ``

Input 2:

`` arr[] = {-1, 1, -2, 3, -2, 2, 4, 9, 8}``

Output 2:

`` {3, -2, 1, -1, 2, -2, 4, 9, 8}``

Explanation:

``Extra positive elements are put at the end, and rearrange all positive and negative elements to occupy alternate positions. ``

Also see, Euclid GCD Algorithm

Brute Force Approach

The idea is very simple, we will make two temporary arrays and store positive and negative elements in that arrays from the original array. Then we will traverse the original array, and take one positive and negative from the temporary array, and as soon as either of them gets over, we will push the remaining elements of the other temporary array into the original one.

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

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.

Until then, Keep Learning and Keep Coding.

Live masterclass