Given an array of positive and negative numbers, arrange them such that all negative integers appear before all the positive integers in the array without using any additional data structure like a hash table, arrays, etc. The order of appearance should be maintained.
Examples:
Input: [12 11 -13 -5 6 -7 5 -3 -6] Output: [-13 -5 -7 -3 -6 12 11 6 5]
A simple solution is to use another array. We copy all elements of the original array to a new array. We then traverse the new array and copy all negative and positive elements back into the original array one by one. This approach is discussed. The problem with this approach is that it uses an auxiliary array and we’re not allowed to use any data structure to solve this problem.
One approach that does not use any data structure is to use the partition process of QuickSort. The idea is to consider 0 as a pivot and divide the array around it. The problem with this approach is that it changes the relative order of elements. A similar partition process is discussed here.
Let’s now discuss a few methods which do not use any other data structure and also preserve the relative order of elements.
Approach 1: Modified Partition Process of Quick Sort
We can reverse the order of positive numbers whenever the relative order is changed. This will happen if there are more than one positive element between the last negative number in the left subarray and the current negative element.
Below are the steps on how this will happen:
Current Array :- [Ln, P1, P2, P3, N1, .......]
Here, Ln is the left subarray(can be empty) that contains only negative elements. P1, P2, P3 are the positive numbers and N1
is the negative number that we want to move at correct place.
If difference of indices between positive number and negative number is greater than 1,
1. Swap P1 and N1, we get [Ln, N1, P2, P3, P1, ......]
2. Rotate array by one position to right, i.e. rotate array [P2, P3, P1], we get [Ln, N1, P1, P2, P3, ......]
Below is the implementation for the same as follows:
C++
// C++ program to Rearrange positive and negative// numbers in a array#include <bits/stdc++.h>using namespace std;// A utility function to print an array of size nvoid printArray(int arr[], int n){ for (int i = 0; i < n; i++) cout<<arr[i]<<" ";}void rotateSubArray(int arr[], int l, int r) {int temp = arr[r];for (int j = r; j > l - 1; j--) { arr[j] = arr[j - 1];}arr[l] = temp;} void moveNegative(int arr[], int n) { int last_negative_index = -1; for (int i = 0; i < n; i++) { if (arr[i] < 0) { last_negative_index += 1; int temp = arr[i]; arr[i] = arr[last_negative_index]; arr[last_negative_index] = temp; // Done to manage order too if (i - last_negative_index >= 2) rotateSubArray(arr, last_negative_index + 1, i); }}} // Driver Codeint main(){ int arr[] = { 5, 5, -3, 4, -8, 0, -7, 3, -9, -3, 9, -2, 1 }; int n = sizeof(arr) / sizeof(arr[0]); moveNegative(arr, n); printArray(arr, n); return 0;}// This code is contributed by Aarti_Rathi |
Java
// Java program for// moving negative numbers to left// while maintaining the orderimport java.io.*;class GFG { static int[] rotateSubArray(int[] arr, int l, int r) { int temp = arr[r]; for (int j = r; j > l - 1; j--) { arr[j] = arr[j - 1]; } arr[l] = temp; return arr; } static int[] moveNegative(int[] arr) { int last_negative_index = -1; for (int i = 0; i < arr.length; i++) { if (arr[i] < 0) { last_negative_index += 1; int temp = arr[i]; arr[i] = arr[last_negative_index]; arr[last_negative_index] = temp; // Done to manage order too if (i - last_negative_index >= 2) rotateSubArray( arr, last_negative_index + 1, i); } } return arr; } // Driver Code public static void main(String args[]) { int[] arr = { 5, 5, -3, 4, -8, 0, -7, 3, -9, -3, 9, -2, 1 }; arr = moveNegative(arr); for (int i : arr) { System.out.print(i + " "); } }}// This code is contributed by Saurabh Jaiswal |
Python3
# Python 3 program for# moving negative numbers to left# while maintaining the orderclass Solution: def rotateSubArray(self, arr, l, r): temp = arr[r] for j in range(r, l-1, -1): arr[j] = arr[j-1] arr[l] = temp return arr def moveNegative(self, arr): last_negative_index = -1 for i in range(len(arr)): if arr[i] < 0: last_negative_index += 1 arr[i], arr[last_negative_index] = arr[last_negative_index], arr[i] # Done to manage order too if i - last_negative_index >= 2: self.rotateSubArray(arr, last_negative_index+1, i) return arr# Driver Codeif __name__ == '__main__': arr = [5, 5, -3, 4, -8, 0, -7, 3, -9, -3, 9, -2, 1] ob = Solution() ob.moveNegative(arr) for i in arr: print(i, end=' ') print()# This code is contributed by Kapil Bansal(devkapilbansal) |
C#
// C# program for// moving negative numbers to left// while maintaining the orderusing System;class GFG { static int[] rotateSubArray(int[] arr, int l, int r) { int temp = arr[r]; for (int j = r; j > l - 1; j--) { arr[j] = arr[j - 1]; } arr[l] = temp; return arr; } static int[] moveNegative(int[] arr) { int last_negative_index = -1; for (int i = 0; i < arr.Length; i++) { if (arr[i] < 0) { last_negative_index += 1; int temp = arr[i]; arr[i] = arr[last_negative_index]; arr[last_negative_index] = temp; // Done to manage order too if (i - last_negative_index >= 2) rotateSubArray(arr, last_negative_index + 1, i); } } return arr; } // Driver Code public static void Main() { int[] arr = { 5, 5, -3, 4, -8, 0, -7, 3, -9, -3, 9, -2, 1 }; arr = moveNegative(arr); foreach (int i in arr) { Console.Write(i + " "); } }}// This code is contributed by gfgking. |
Javascript
<script>// JavaScript program for// moving negative numbers to left// while maintaining the orderclass Solution{ rotateSubArray(arr, l, r){ let temp = arr[r] for(let j = r;j > l-1;j--){ arr[j] = arr[j-1] } arr[l] = temp return arr } moveNegative(arr){ let last_negative_index = -1 for(let i=0;i<arr.length;i++){ if(arr[i] < 0){ last_negative_index += 1 let temp = arr[i]; arr[i] = arr[last_negative_index]; arr[last_negative_index] = temp; // Done to manage order too if(i - last_negative_index >= 2) this.rotateSubArray(arr, last_negative_index+1, i) } } return arr }}// Driver Codelet arr = [5, 5, -3, 4, -8, 0, -7, 3, -9, -3, 9, -2, 1]let ob = new Solution()ob.moveNegative(arr)for(let i of arr){ document.write(i,' ')}// This code is contributed by shinjanpatra</script> |
PHP
<?php// A utility function to print an array of size nfunction printArray($arr, $n) { for ($i = 0; $i < $n; $i++) { echo $arr[$i] . " "; }}function rotateSubArray(&$arr, $l, $r) { $temp = $arr[$r]; for ($j = $r; $j > $l - 1; $j--) { $arr[$j] = $arr[$j - 1]; } $arr[$l] = $temp;}function moveNegative(&$arr, $n) { $last_negative_index = -1; for ($i = 0; $i < $n; $i++) { if ($arr[$i] < 0) { $last_negative_index += 1; $temp = $arr[$i]; $arr[$i] = $arr[$last_negative_index]; $arr[$last_negative_index] = $temp; // Done to manage order too if ($i - $last_negative_index >= 2) { rotateSubArray($arr, $last_negative_index + 1, $i); } } }}$arr = array(5, 5, -3, 4, -8, 0, -7, 3, -9, -3, 9, -2, 1);$n = sizeof($arr) / sizeof($arr[0]);moveNegative($arr, $n);printArray($arr, $n);?> |
Output
-3 -8 -7 -9 -3 -2 5 5 4 0 3 9 1
Time Complexity: O(n2)
Auxiliary Space: O(1)
Approach 2: Modified Insertion Sort
We can modify insertion sort to solve this problem.
Algorithm:
Loop from i = 1 to n - 1.
a) If the current element is positive, do nothing.
b) If the current element arr[i] is negative, we
insert it into sequence arr[0..i-1] such that
all positive elements in arr[0..i-1] are shifted
one position to their right and arr[i] is inserted
at index of first positive element.
Below is the implementation –
C++
// C++ program to Rearrange positive and negative// numbers in a array#include <stdio.h>// A utility function to print an array of size nvoid printArray(int arr[], int n){ for (int i = 0; i < n; i++) printf("%d ", arr[i]); printf("\n");}// Function to Rearrange positive and negative// numbers in a arrayvoid RearrangePosNeg(int arr[], int n){ int key, j; for (int i = 1; i < n; i++) { key = arr[i]; // if current element is positive // do nothing if (key > 0) continue; /* if current element is negative, shift positive elements of arr[0..i-1], to one position to their right */ j = i - 1; while (j >= 0 && arr[j] > 0) { arr[j + 1] = arr[j]; j = j - 1; } // Put negative element at its right position arr[j + 1] = key; }}/* Driver program to test above functions */int main(){ int arr[] = { -12, 11, -13, -5, 6, -7, 5, -3, -6 }; int n = sizeof(arr) / sizeof(arr[0]); RearrangePosNeg(arr, n); printArray(arr, n); return 0;} |
Java
// Java program to Rearrange positive// and negative numbers in a arrayimport java.io.*;class GFG { // A utility function to print // an array of size n static void printArray(int arr[], int n) { for (int i = 0; i < n; i++) System.out.print(arr[i] + " "); System.out.println(); } // Function to Rearrange positive and negative // numbers in a array static void RearrangePosNeg(int arr[], int n) { int key, j; for (int i = 1; i < n; i++) { key = arr[i]; // if current element is positive // do nothing if (key > 0) continue; /* if current element is negative, shift positive elements of arr[0..i-1], to one position to their right */ j = i - 1; while (j >= 0 && arr[j] > 0) { arr[j + 1] = arr[j]; j = j - 1; } // Put negative element at its right position arr[j + 1] = key; } } // Driver program public static void main(String[] args) { int arr[] = { -12, 11, -13, -5, 6, -7, 5, -3, -6 }; int n = arr.length; RearrangePosNeg(arr, n); printArray(arr, n); }}// This code is contributed by vt_m. |
Python 3
# Python 3 program to Rearrange positive# and negative numbers in a array# A utility function to print# an array of size ndef printArray(arr, n): for i in range(n): print(arr[i], end=" ") print()# Function to Rearrange positive# and negative numbers in a arraydef RearrangePosNeg(arr, n): for i in range(1, n): key = arr[i] # if current element is positive # do nothing if (key > 0): continue ''' if current element is negative, shift positive elements of arr[0..i-1], to one position to their right ''' j = i - 1 while (j >= 0 and arr[j] > 0): arr[j + 1] = arr[j] j = j - 1 # Put negative element at its # right position arr[j + 1] = key# Driver Codeif __name__ == "__main__": arr = [-12, 11, -13, -5, 6, -7, 5, -3, -6] n = len(arr) RearrangePosNeg(arr, n) printArray(arr, n)# This code is contributed# by ChitraNayal |
C#
// C# program to Rearrange positive// and negative numbers in a arrayusing System;class GFG { // A utility function to print // an array of size n static void printArray(int[] arr, int n) { for (int i = 0; i < n; i++) Console.Write(arr[i] + " "); Console.WriteLine(); } // Function to Rearrange positive and negative // numbers in a array static void RearrangePosNeg(int[] arr, int n) { int key, j; for (int i = 1; i < n; i++) { key = arr[i]; // if current element is positive // do nothing if (key > 0) continue; /* if current element is negative, shift positive elements of arr[0..i-1], to one position to their right */ j = i - 1; while (j >= 0 && arr[j] > 0) { arr[j + 1] = arr[j]; j = j - 1; } // Put negative element at its right position arr[j + 1] = key; } } // Driver program public static void Main() { int[] arr = { -12, 11, -13, -5, 6, -7, 5, -3, -6 }; int n = arr.Length; RearrangePosNeg(arr, n); printArray(arr, n); }}// This code is contributed by vt_m. |
PHP
<?php// PHP program to Rearrange positive // and negative numbers in a array// A utility function to print // an array of size nfunction printArray($arr, $n){ for ($i = 0; $i < $n; $i++) echo($arr[$i] . " ");}// Function to Rearrange positive and negative// numbers in a arrayfunction RearrangePosNeg(&$arr, $n){ $key; $j; for($i = 1; $i < $n; $i++) { $key = $arr[$i]; // if current element is positive // do nothing if ($key > 0) continue; /* if current element is negative, shift positive elements of arr[0..i-1], to one position to their right */ $j = $i - 1; while ($j >= 0 && $arr[$j] > 0) { $arr[$j + 1] = $arr[$j]; $j = $j - 1; } // Put negative element at its right position $arr[$j + 1] = $key; }}// Driver program { $arr = array( -12, 11, -13, -5, 6, -7, 5, -3, -6 ); $n = sizeof($arr); RearrangePosNeg($arr, $n); printArray($arr, $n);}// This code is contributed by Code_Mech. |
Javascript
<script>// Javascript program to Rearrange positive// and negative numbers in a array // A utility function to print // an array of size n function printArray(arr, n) { for (let i = 0; i < n; i++) document.write(arr[i] + " "); document.write("<br />"); } // Function to Rearrange positive and negative // numbers in a array function RearrangePosNeg(arr, n) { let key, j; for (let i = 1; i < n; i++) { key = arr[i]; // if current element is positive // do nothing if (key > 0) continue; /* if current element is negative, shift positive elements of arr[0..i-1], to one position to their right */ j = i - 1; while (j >= 0 && arr[j] > 0) { arr[j + 1] = arr[j]; j = j - 1; } // Put negative element at its right position arr[j + 1] = key; } } // Driver Code let arr = [ -12, 11, -13, -5, 6, -7, 5, -3, -6 ]; let n = arr.length; RearrangePosNeg(arr, n); printArray(arr, n); </script> |
Output
-12 -13 -5 -7 -3 -6 11 6 5
Time Complexity: O(n2)
Auxiliary Space: O(1)
We have maintained the order of appearance and have not used any other data structure.
Approach 2: Optimized Merge Sort
Merge method of standard merge sort algorithm can be modified to solve this problem. While merging two sorted halves say left and right, we need to merge in such a way that negative part of left and right sub-array is copied first followed by positive part of left and right sub-array.
Below is the implementation of the idea as shown below as follows:
C++
// C++ program to Rearrange positive and negative// numbers in a array#include <iostream>using namespace std;/* Function to print an array */void printArray(int A[], int size){ for (int i = 0; i < size; i++) cout << A[i] << " "; cout << endl;}// Merges two subarrays of arr[].// First subarray is arr[l..m]// Second subarray is arr[m+1..r]void merge(int arr[], int l, int m, int r){ int i, j, k; int n1 = m - l + 1; int n2 = r - m; /* create temp arrays */ int L[n1], R[n2]; /* Copy data to temp arrays L[] and R[] */ for (i = 0; i < n1; i++) L[i] = arr[l + i]; for (j = 0; j < n2; j++) R[j] = arr[m + 1 + j]; /* Merge the temp arrays back into arr[l..r]*/ i = 0; // Initial index of first subarray j = 0; // Initial index of second subarray k = l; // Initial index of merged subarray // Note the order of appearance of elements should // be maintained - we copy elements of left subarray // first followed by that of right subarray // copy negative elements of left subarray while (i < n1 && L[i] < 0) arr[k++] = L[i++]; // copy negative elements of right subarray while (j < n2 && R[j] < 0) arr[k++] = R[j++]; // copy positive elements of left subarray while (i < n1) arr[k++] = L[i++]; // copy positive elements of right subarray while (j < n2) arr[k++] = R[j++];}// Function to Rearrange positive and negative// numbers in a arrayvoid RearrangePosNeg(int arr[], int l, int r){ if (l < r) { // Same as (l + r)/2, but avoids overflow for // large l and h int m = l + (r - l) / 2; // Sort first and second halves RearrangePosNeg(arr, l, m); RearrangePosNeg(arr, m + 1, r); merge(arr, l, m, r); }}/* Driver program to test above functions */int main(){ int arr[] = { -12, 11, -13, -5, 6, -7, 5, -3, -6 }; int arr_size = sizeof(arr) / sizeof(arr[0]); RearrangePosNeg(arr, 0, arr_size - 1); printArray(arr, arr_size); return 0;} |
Java
// Java program to Rearrange positive// and negative numbers in a arrayimport java.io.*;class GFG { /* Function to print an array */ static void printArray(int A[], int size) { for (int i = 0; i < size; i++) System.out.print(A[i] + " "); System.out.println(); } // Merges two subarrays of arr[]. // First subarray is arr[l..m] // Second subarray is arr[m+1..r] static void merge(int arr[], int l, int m, int r) { int i, j, k; int n1 = m - l + 1; int n2 = r - m; /* create temp arrays */ int L[] = new int[n1]; int R[] = new int[n2]; /* Copy data to temp arrays L[] and R[] */ for (i = 0; i < n1; i++) L[i] = arr[l + i]; for (j = 0; j < n2; j++) R[j] = arr[m + 1 + j]; /* Merge the temp arrays back into arr[l..r]*/ // Initial index of first subarray i = 0; // Initial index of second subarray j = 0; // Initial index of merged subarray k = l; // Note the order of appearance of elements should // be maintained - we copy elements of left subarray // first followed by that of right subarray // copy negative elements of left subarray while (i < n1 && L[i] < 0) arr[k++] = L[i++]; // copy negative elements of right subarray while (j < n2 && R[j] < 0) arr[k++] = R[j++]; // copy positive elements of left subarray while (i < n1) arr[k++] = L[i++]; // copy positive elements of right subarray while (j < n2) arr[k++] = R[j++]; } // Function to Rearrange positive and negative // numbers in a array static void RearrangePosNeg(int arr[], int l, int r) { if (l < r) { // Same as (l + r)/2, but avoids overflow for // large l and h int m = l + (r - l) / 2; // Sort first and second halves RearrangePosNeg(arr, l, m); RearrangePosNeg(arr, m + 1, r); merge(arr, l, m, r); } } // Driver program public static void main(String[] args) { int arr[] = { -12, 11, -13, -5, 6, -7, 5, -3, -6 }; int arr_size = arr.length; RearrangePosNeg(arr, 0, arr_size - 1); printArray(arr, arr_size); }}// This code is contributed by vt_m. |
Python3
# Python3 program to Rearrange positive# and negative numbers in a array# Function to print an arraydef printArray(A, size): for i in range(size): print(A[i], end=" ") print()# Merges two subarrays of arr[].# First subarray is arr[l..m]# Second subarray is arr[m + 1..r]def merge(arr, l, m, r): i, j, k = 0, 0, 0 n1 = m - l + 1 n2 = r - m # create temp arrays */ L = [arr[l + i] for i in range(n1)] R = [arr[m + 1 + j] for j in range(n2)] # Merge the temp arrays back into arr[l..r]*/ i = 0 # Initial index of first subarray j = 0 # Initial index of second subarray k = l # Initial index of merged subarray # Note the order of appearance of elements # should be maintained - we copy elements # of left subarray first followed by that # of right subarray # copy negative elements of left subarray while (i < n1 and L[i] < 0): arr[k] = L[i] k += 1 i += 1 # copy negative elements of right subarray while (j < n2 and R[j] < 0): arr[k] = R[j] k += 1 j += 1 # copy positive elements of left subarray while (i < n1): arr[k] = L[i] k += 1 i += 1 # copy positive elements of right subarray while (j < n2): arr[k] = R[j] k += 1 j += 1# Function to Rearrange positive and# negative numbers in a arraydef RearrangePosNeg(arr, l, r): if(l < r): # Same as (l + r)/2, but avoids # overflow for large l and h m = l + (r - l) // 2 # Sort first and second halves RearrangePosNeg(arr, l, m) RearrangePosNeg(arr, m + 1, r) merge(arr, l, m, r)# Driver Codearr = [-12, 11, -13, -5, 6, -7, 5, -3, -6]arr_size = len(arr)RearrangePosNeg(arr, 0, arr_size - 1)printArray(arr, arr_size)# This code is contributed by# mohit kumar 29 |
C#
// C# program to Rearrange positive// and negative numbers in a arrayusing System;class GFG { /* Function to print an array */ static void printArray(int[] A, int size) { for (int i = 0; i < size; i++) Console.Write(A[i] + " "); Console.WriteLine(); } // Merges two subarrays of arr[]. // First subarray is arr[l..m] // Second subarray is arr[m+1..r] static void merge(int[] arr, int l, int m, int r) { int i, j, k; int n1 = m - l + 1; int n2 = r - m; /* create temp arrays */ int[] L = new int[n1]; int[] R = new int[n2]; /* Copy data to temp arrays L[] and R[] */ for (i = 0; i < n1; i++) L[i] = arr[l + i]; for (j = 0; j < n2; j++) R[j] = arr[m + 1 + j]; /* Merge the temp arrays back into arr[l..r]*/ // Initial index of first subarray i = 0; // Initial index of second subarray j = 0; // Initial index of merged subarray k = l; // Note the order of appearance of elements should // be maintained - we copy elements of left subarray // first followed by that of right subarray // copy negative elements of left subarray while (i < n1 && L[i] < 0) arr[k++] = L[i++]; // copy negative elements of right subarray while (j < n2 && R[j] < 0) arr[k++] = R[j++]; // copy positive elements of left subarray while (i < n1) arr[k++] = L[i++]; // copy positive elements of right subarray while (j < n2) arr[k++] = R[j++]; } // Function to Rearrange positive and negative // numbers in a array static void RearrangePosNeg(int[] arr, int l, int r) { if (l < r) { // Same as (l + r)/2, but avoids overflow for // large l and h int m = l + (r - l) / 2; // Sort first and second halves RearrangePosNeg(arr, l, m); RearrangePosNeg(arr, m + 1, r); merge(arr, l, m, r); } } // Driver program public static void Main() { int[] arr = { -12, 11, -13, -5, 6, -7, 5, -3, -6 }; int arr_size = arr.Length; RearrangePosNeg(arr, 0, arr_size - 1); printArray(arr, arr_size); }}// This code is contributed by vt_m. |
Javascript
<script>// javascript program to Rearrange positive and negative// numbers in a array /* Function to print an array */ function printArray(A , size) { for (i = 0; i < size; i++) document.write(A[i] + " "); document.write('<br>'); ; } /* Function to reverse an array. An array can bereversed in O(n) time and O(1) space. */ function reverse(arr , l , r) { if (l < r) { arr = swap(arr, l, r); reverse(arr, ++l, --r); } } // Merges two subarrays of arr. // First subarray is arr[l..m] // Second subarray is arr[m+1..r] function merge(arr , l , m , r) { // Initial index of 1st subarray var i = l; // Initial index of IInd var j = m + 1; while (i <= m && arr[i] < 0) i++; // arr[i..m] is positive while (j <= r && arr[j] < 0) j++; // arr[j..r] is positive // reverse positive part of // left sub-array (arr[i..m]) reverse(arr, i, m); // reverse negative part of // right sub-array (arr[m+1..j-1]) reverse(arr, m + 1, j - 1); // reverse arr[i..j-1] reverse(arr, i, j - 1); } // Function to Rearrange positive and negative // numbers in a array function RearrangePosNeg(arr , l , r) { if (l < r) { // Same as (l+r)/2, but avoids overflow for // large l and h var m = l + parseInt((r - l) / 2); // Sort first and second halves RearrangePosNeg(arr, l, m); RearrangePosNeg(arr, m + 1, r); merge(arr, l, m, r); } } function swap(arr , i , j) { var temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; return arr; } /* Driver code*/ var arr = [ -12, 11, -13, -5, 6, -7, 5, -3, -6 ]; var arr_size = arr.length; RearrangePosNeg(arr, 0, arr_size - 1); printArray(arr, arr_size);// This code contributed by shikhasingrajput </script> |
Output
-12 -13 -5 -7 -3 -6 11 6 5
Time complexity: O(n log n).
Auxiliary Space: O(n1 + n2 + log n), log n, as implicit stack is used due to recursive call
The problem with this approach is we are using an auxiliary array for merging but we’re not allowed to use any data structure to solve this problem. We can do merging in place without using any data structure. The idea is taken from here.
Let Ln and Lp denote the negative part and positive part of the left sub-array respectively. Similarly, Rn and Rp denote the negative and positive parts of the right sub-array respectively.
Below are the steps to convert [Ln Lp Rn Rp] to [Ln Rn Lp Rp] without using extra space.
1. Reverse Lp and Rn. We get [Lp] -> [Lp'] and [Rn] -> [Rn']
[Ln Lp Rn Rp] -> [Ln Lp’ Rn’ Rp]
2. Reverse [Lp’ Rn’]. We get [Rn Lp].
[Ln Lp’ Rn’ Rp] -> [Ln Rn Lp Rp]
Below is the implementation of the above idea:
C++
// C++ program to Rearrange positive and negative// numbers in a array#include <bits/stdc++.h>using namespace std;/* Function to print an array */void printArray(int A[], int size){ for (int i = 0; i < size; i++) cout << A[i] << " "; cout << endl;}/* Function to reverse an array. An array can bereversed in O(n) time and O(1) space. */void reverse(int arr[], int l, int r){ if (l < r) { swap(arr[l], arr[r]); reverse(arr, ++l, --r); }}// Merges two subarrays of arr[].// First subarray is arr[l..m]// Second subarray is arr[m+1..r]void merge(int arr[], int l, int m, int r){ int i = l; // Initial index of 1st subarray int j = m + 1; // Initial index of IInd while (i <= m && arr[i] < 0) i++; // arr[i..m] is positive while (j <= r && arr[j] < 0) j++; // arr[j..r] is positive // reverse positive part of // left sub-array (arr[i..m]) reverse(arr, i, m); // reverse negative part of // right sub-array (arr[m+1..j-1]) reverse(arr, m + 1, j - 1); // reverse arr[i..j-1] reverse(arr, i, j - 1);}// Function to Rearrange positive and negative// numbers in a arrayvoid RearrangePosNeg(int arr[], int l, int r){ if (l < r) { // Same as (l+r)/2, but avoids overflow for // large l and h int m = l + (r - l) / 2; // Sort first and second halves RearrangePosNeg(arr, l, m); RearrangePosNeg(arr, m + 1, r); merge(arr, l, m, r); }}/* Driver code */int main(){ int arr[] = { -12, 11, -13, -5, 6, -7, 5, -3, -6 }; int arr_size = sizeof(arr) / sizeof(arr[0]); RearrangePosNeg(arr, 0, arr_size - 1); printArray(arr, arr_size); return 0;} |
Java
// Java program to Rearrange positive and negative// numbers in a arrayimport java.io.*;class GFG { /* Function to print an array */ static void printArray(int A[], int size) { for (int i = 0; i < size; i++) System.out.print(A[i] + " "); System.out.println(""); ; } /* Function to reverse an array. An array can bereversed in O(n) time and O(1) space. */ static void reverse(int arr[], int l, int r) { if (l < r) { arr = swap(arr, l, r); reverse(arr, ++l, --r); } } // Merges two subarrays of arr[]. // First subarray is arr[l..m] // Second subarray is arr[m+1..r] static void merge(int arr[], int l, int m, int r) { int i = l; // Initial index of 1st subarray int j = m + 1; // Initial index of IInd while (i <= m && arr[i] < 0) i++; // arr[i..m] is positive while (j <= r && arr[j] < 0) j++; // arr[j..r] is positive // reverse positive part of // left sub-array (arr[i..m]) reverse(arr, i, m); // reverse negative part of // right sub-array (arr[m+1..j-1]) reverse(arr, m + 1, j - 1); // reverse arr[i..j-1] reverse(arr, i, j - 1); } // Function to Rearrange positive and negative // numbers in a array static void RearrangePosNeg(int arr[], int l, int r) { if (l < r) { // Same as (l+r)/2, but avoids overflow for // large l and h int m = l + (r - l) / 2; // Sort first and second halves RearrangePosNeg(arr, l, m); RearrangePosNeg(arr, m + 1, r); merge(arr, l, m, r); } } static int[] swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; return arr; } /* Driver code*/ public static void main(String[] args) { int arr[] = { -12, 11, -13, -5, 6, -7, 5, -3, -6 }; int arr_size = arr.length; RearrangePosNeg(arr, 0, arr_size - 1); printArray(arr, arr_size); }}// This code has been contributed by 29AjayKumar |
Python3
# Python3 program to Rearrange positive# and negative numbers in an array# Function to print an arraydef printArray(A, size): for i in range(0, size): print(A[i], end=" ") print()# Function to reverse an array. An array can# be reversed in O(n) time and O(1) space.def reverse(arr, l, r): if l < r: arr[l], arr[r] = arr[r], arr[l] l, r = l + 1, r - 1 reverse(arr, l, r)# Merges two subarrays of arr[].# First subarray is arr[l..m]# Second subarray is arr[m + 1..r]def merge(arr, l, m, r): i = l # Initial index of 1st subarray j = m + 1 # Initial index of IInd while i <= m and arr[i] < 0: i += 1 # arr[i..m] is positive while j <= r and arr[j] < 0: j += 1 # arr[j..r] is positive # reverse positive part of left # sub-array (arr[i..m]) reverse(arr, i, m) # reverse negative part of right # sub-array (arr[m + 1..j-1]) reverse(arr, m + 1, j - 1) # reverse arr[i..j-1] reverse(arr, i, j - 1)# Function to Rearrange positive# and negative numbers in a arraydef RearrangePosNeg(arr, l, r): if l < r: # Same as (l + r)/2, but avoids # overflow for large l and h m = l + (r - l) // 2 # Sort first and second halves RearrangePosNeg(arr, l, m) RearrangePosNeg(arr, m + 1, r) merge(arr, l, m, r)# Driver Codeif __name__ == "__main__": arr = [-12, 11, -13, -5, 6, -7, 5, -3, -6] arr_size = len(arr) RearrangePosNeg(arr, 0, arr_size - 1) printArray(arr, arr_size)# This code is contributed by Rituraj Jain |
C#
// C# program to Rearrange positive and negative// numbers in a arrayusing System;class GFG { /* Function to print an array */ static void printArray(int[] A, int size) { for (int i = 0; i < size; i++) Console.Write(A[i] + " "); Console.WriteLine(""); ; } /* Function to reverse an array. An array can bereversed in O(n) time and O(1) space. */ static void reverse(int[] arr, int l, int r) { if (l < r) { arr = swap(arr, l, r); reverse(arr, ++l, --r); } } // Merges two subarrays of arr[]. // First subarray is arr[l..m] // Second subarray is arr[m+1..r] static void merge(int[] arr, int l, int m, int r) { int i = l; // Initial index of 1st subarray int j = m + 1; // Initial index of IInd while (i <= m && arr[i] < 0) i++; // arr[i..m] is positive while (j <= r && arr[j] < 0) j++; // arr[j..r] is positive // reverse positive part of // left sub-array (arr[i..m]) reverse(arr, i, m); // reverse negative part of // right sub-array (arr[m+1..j-1]) reverse(arr, m + 1, j - 1); // reverse arr[i..j-1] reverse(arr, i, j - 1); } // Function to Rearrange positive and negative // numbers in a array static void RearrangePosNeg(int[] arr, int l, int r) { if (l < r) { // Same as (l+r)/2, but avoids overflow for // large l and h int m = l + (r - l) / 2; // Sort first and second halves RearrangePosNeg(arr, l, m); RearrangePosNeg(arr, m + 1, r); merge(arr, l, m, r); } } static int[] swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; return arr; } /* Driver code*/ public static void Main() { int[] arr = { -12, 11, -13, -5, 6, -7, 5, -3, -6 }; int arr_size = arr.Length; RearrangePosNeg(arr, 0, arr_size - 1); printArray(arr, arr_size); }}/* This code contributed by PrinciRaj1992 */ |
Javascript
<script>// Javascript program to Rearrange positive and negative// numbers in a array /* Function to print an array */ function printArray(A,size) { for (let i = 0; i < size; i++) document.write(A[i] + " "); document.write("<br>"); } /* Function to reverse an array. An array can bereversed in O(n) time and O(1) space. */ function reverse(arr,l,r) { if (l < r) { arr = swap(arr, l, r); reverse(arr, ++l, --r); } } // Merges two subarrays of arr[]. // First subarray is arr[l..m] // Second subarray is arr[m+1..r] function merge(arr,l,m,r) { let i = l; // Initial index of 1st subarray let j = m + 1; // Initial index of IInd while (i <= m && arr[i] < 0) i++; // arr[i..m] is positive while (j <= r && arr[j] < 0) j++; // arr[j..r] is positive // reverse positive part of // left sub-array (arr[i..m]) reverse(arr, i, m); // reverse negative part of // right sub-array (arr[m+1..j-1]) reverse(arr, m + 1, j - 1); // reverse arr[i..j-1] reverse(arr, i, j - 1); } // Function to Rearrange positive and negative // numbers in a array function RearrangePosNeg(arr,l,r) { if (l < r) { // Same as (l+r)/2, but avoids overflow for // large l and h let m = l + Math.floor((r - l) / 2); // Sort first and second halves RearrangePosNeg(arr, l, m); RearrangePosNeg(arr, m + 1, r); merge(arr, l, m, r); } } function swap(arr,i,j) { let temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; return arr; } /* Driver code*/ let arr=[-12, 11, -13, -5, 6, -7, 5, -3, -6 ]; let arr_size = arr.length; RearrangePosNeg(arr, 0, arr_size - 1); printArray(arr, arr_size); // This code is contributed by unknown2108</script> |
Output
-12 -13 -5 -7 -3 -6 11 6 5
Time complexity: O(n log n), O(Log n) space for recursive calls, and no additional data structure.
Auxiliary Space: O(log n), as implicit stack is used due to recursive call
Approach 4: Using Sliding Window with two pointer technique
This technique utilises sliding window of positive numbers to shift negative numbers to the start of the window, while moving forward.
C++
#include <iostream>using namespace std;void rearrangePosNegWithOrder(int *arr, int size){ int i = 0, j = 0; while (j < size) { if (arr[j] >= 0) { j++; } else { for (int k = j; k > i; k--) { int temp = arr[k]; arr[k] = arr[k - 1]; arr[k - 1] = temp; } i++; j++; } }}int main(){ int arr[] = { -12, 11, -13, -5, 6, -7, 5, -3, -6 }; int size = *(&arr + 1) - arr; rearrangePosNegWithOrder(arr, size); for (int i : arr) { cout << i; cout << " "; } return 0;} |
Java
import java.io.*;class GFG { // Here the size of window increases as it encounters // positive numbers public static void rearrangePosNegWithOrder(int[] arr) { int i = 0, j = 0; while (j < arr.length) { if (arr[j] >= 0) { j++; } else { for (int k = j; k > i; k--) { int temp = arr[k]; arr[k] = arr[k - 1]; arr[k - 1] = temp; } i++; j++; } } } public static void main(String[] args) { int arr[] = { -12, 11, -13, -5, 6, -7, 5, -3, -6 }; rearrangePosNegWithOrder(arr); for (int i : arr) { System.out.print(i + " "); } }} |
Python3
def rearrangePosNegWithOrder(arr, size): i = 0 j = 0 while(j < size): if(arr[j] >= 0): j += 1 else: for k in range(j,i,-1): temp = arr[k] arr[k] = arr[k - 1] arr[k - 1] = temp i += 1 j += 1 return arr # driver codearr = [-12, 11, -13, -5, 6, -7, 5, -3, -6 ]size = len(arr)aux = rearrangePosNegWithOrder(arr, size)for i in aux: print(i,end=" ")# This code is contributed by Vibhu Karnwal |
C#
// C# code addition for the above approachusing System;public class GFG { // Here the size of window increases as it encounters // positive numbers public static void rearrangePosNegWithOrder(int[] arr) { int i = 0, j = 0; while (j < arr.Length) { if (arr[j] >= 0) { j++; } else { for (int k = j; k > i; k--) { int temp = arr[k]; arr[k] = arr[k - 1]; arr[k - 1] = temp; } i++; j++; } } } static public void Main() { // Code int[] arr = { -12, 11, -13, -5, 6, -7, 5, -3, -6 }; rearrangePosNegWithOrder(arr); foreach(int i in arr) { Console.Write(i + " "); } }}// This code is contributed by lokesh |
Javascript
// JS code for above approachfunction rearrangePosNegWithOrder(arr, size) { let i = 0, j = 0; while (j < size) { if (arr[j] >= 0) { j++; } else { for (let k = j; k > i; k--) { let temp = arr[k]; arr[k] = arr[k - 1]; arr[k - 1] = temp; } i++; j++; } }}let arr = [-12, 11, -13, -5, 6, -7, 5, -3, -6];let size = arr.length;rearrangePosNegWithOrder(arr, size);for (let i = 0; i < size; i++) { console.log(arr[i]);}// This code is contributed by adityamaharshi21 |
Output
-12 -13 -5 -7 -3 -6 11 6 5
Time Complexity: O(n*window)
Auxiliary Space: O(1), since no extra space has been taken.
This article is contributed by Aditya Goel. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or if you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
