Rearrange positive and negative numbers with constant extra space

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.

// Java program for

// moving negative numbers to left

// while maintaining the order

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 + " ");

}

}

}

Output

-3 -8 -7 -9 -3 -2 5 5 4 0 3 9 1

Time Complexity: O(n2)
Auxiliary Space: O(1)