Introduction
This article will look at the Rearrangement of positive and negative numbers and the order of numbers that need to be maintained. 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 negative integers come before positive integers and the order in which they come should remain the same.
Let's Discuss the sample example to understand the problem better.
Sample Examples
Input:
arr[] = {-1,2,1,3,-1,-2,-3}
Output:
{-1, -1, -2, -3, 2, 1, 3}
Explanation: In the above example, we have rearranged the numbers so that all negative comes before positive, and the order of elements is the same.
Input:
arr[] = {-1, 1, -2, 3, -2, 2, 4, 9, 8}
Output:
{-1, -2, -2, 1, 3, 2, 4, 9, 8}
Explanation: In the above example, we have rearranged the numbers so that all negative comes before positive, and the order of elements is the same.
Solution Approach
The idea is simple; we will use the C++ inbuilt function and a comparator function to modify the sorting function according to our requirements—a few cases needed to be handled in the comparator function. We will have two arguments in the comparator function, namely num1 and num2, and the index will be i and j, and i>j. If the comparator function returns true, then the swap will be done. Otherwise, nothing happens.
Conditions:
num1 index i > num2 index j, The index of the first argument in comparator function is higher.
Condition 1: if(num1>0 && num2>0) || (num1<0 && num2<0) || (num1>0 && num2<0)
Return false,
This condition states that if elements are either positive or negative, don't swap them, and also if the element at jth index is negative and the element at ith index is positive, don't swap them because we need to put negative elements at the front.
Condition 2: if(num1<0 && num2>0) return true
This condition states that if num1<0 and num2>0, the higher index element is negative; therefore, swapping is required, hence return true.
Now we also need to handle the cases if the element is 0. We need to put 0 in between negative and positive elements.
Condition 3: if(num1==0 && num2<0 || num1>0 && num2==0) return false;
This condition states that if element on left of 0 is negative, or element right to 0 is positive then we don’t need to swap any element.
Condition 4: if(num1<0 && num2==0 || num1<0 && num2==0) return true;
This condition states that if element on right of 0 is negative and element on left of 0 is positive then swapping is needed.
Steps of algorithm
- Call the comparator function
- In the comparator function, we have 2 arguments (int num1, int num2), and apply the above four conditions as explained
- Finally, the array we received will be the rearranged array.
Implementation in C++
// C++ program to rearrange postive and negative elements
#include<bits/stdc++.h>
using namespace std;
static bool cmp(int num1, int num2){
// condition 1
if((num1>0 && num2>0) || (num1<0 && num2<0) || (num1>0 && num2<0)) return false;
// condition 2
if(num1<0 && num2>0) return true;
// condition 3
if(num1==0 && num2<0 || num1>0 && num2==0) return false;
// condition 4
if(num1==0 && num2>0 || num1<0 && num2==0) return true;
}
int main(){
vector<int>arr = {-1,2,1,3, 0, 0, -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;
// calling the sort function
sort(arr.begin(), arr.end(), cmp);
cout << "Array after the rearrangement: ";
// Rearrange Array
for(int i=0;i<n;i++) cout << arr[i] << " ";
cout << endl;
}
Output:
Array before the rearrangement: -1 2 1 3 0 0 -1 -2 -3
Array after the rearrangement: -1 -1 -2 -3 0 0 2 1 3Implementation in Python
# python program to rearrange positive and negative elements
from operator import ne
import functools
def compare(num1, num2):
if (num1 > 0 and num2 > 0) or (num1 < 0 and num2 < 0) or (num1 > 0 and num2 < 0):
return 0
# condition 2
if (num1 < 0 and num2 > 0):
return -1
# condition 3
if (num1 == 0 and num2 < 0) or (num1 > 0 and num2 == 0):
return 0
# condition 4
if (num1 == 0 and num2 > 0) or (num1 < 0 and num2 == 0):
return 1
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
arr = sorted(arr, key=functools.cmp_to_key(compare))
# printing the array before rearrangement
print("Array after the rearrangement: ")
# rearrange array
print(arr)
Output:
Array before the rearrangement:
[-1, 2, 1, 3, -1, -2, -3]
Array after the rearrangement:
[-1, -1, -2, -3, 2, 1, 3]
Complexity Analysis
Time Complexity: O(NLogN)
We are doing sorting on the basis of customized conditions, so time complexity is O(NlogN).
Space Complexity: O(1)
We are not using any temporary array, so therefore space complexity is O(1).
Also see, Morris Traversal for Inorder and Rabin Karp Algorithm
84+ registered