**Objective:** Rearrange Positive and Negative Numbers of an Array so that one side you have positive numbers and other side with negative Integers without changing their respective order.

Example: Input : 1 -2 3 -4 5 -6 7 -8 9 -10 ReArranged Output : -2 -4 -6 -8 -10 1 3 5 7 9

**Input:** An array with positive and negative numbers

**Output:** Modified array with positive numbers and negative numbers are on each side of the array.

**Approach:**

**Method 1. **One naive approach is to have another array of same size and navigate the input array and one scan place all the negative numbers to the new array and in second scan place all the positive numbers to new array. Here the Space complexity will be O(n). We have a better solution which can solve this in O(1) space.

**Method 2: Divide and Conquer**

- This approach is similar to merge sort.
- Divide the array into two half, Solve them individually and merge them.
- Tricky part is in merging.

**Merging**: (Negative on left side and positives on the right side)

- Navigate the left half of array till you won’t find a positive integer and reverse the array after that point.(Say that part is called ‘A’)
- Navigate the right half of array till you won’t find a positive integer and reverse the array before that point. (Say that part is called ‘B’)
- Now reverse the those parts from both the array (A and B), See example for better explanation.

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

public class RearrageArrayPositiveNegative { | |

int[] arrA; | |

public RearrageArrayPositiveNegative(int[] arrA) { | |

this.arrA = arrA; | |

} | |

public void divideGroups(int low, int high) { | |

if (low >= high) | |

return; | |

int mid = (low + high) / 2; | |

divideGroups(low, mid); | |

divideGroups(mid + 1 , high); | |

merge(low, mid, high); | |

} | |

public void merge(int low, int mid, int high) { | |

int l = low; | |

int k = mid + 1; | |

while (l <= mid && arrA[l] <= 0) | |

l++; | |

while (k <= high && arrA[k] <= 0) | |

k++; | |

reverse(l, mid); | |

reverse(mid + 1, k – 1); | |

reverse(l, k – 1); | |

} | |

public void reverse(int x, int y) { | |

while (y > x) { | |

int temp = arrA[x]; | |

arrA[x] = arrA[y]; | |

arrA[y] = temp; | |

x++; | |

y—; | |

} | |

} | |

public void display() { | |

for (int i = 0; i < arrA.length; i++) { | |

System.out.print(" " + arrA[i]); | |

} | |

} | |

public static void main(String args[]) { | |

int[] a = { 1, –2, –3, –4, 5, –6, 7, –8, 9, –10, –11, –12, 20 }; | |

RearrageArrayPositiveNegative r = new RearrageArrayPositiveNegative(a); | |

System.out.print("Input : "); | |

r.display(); | |

r.divideGroups(0, a.length – 1); | |

System.out.println(""); | |

System.out.print("ReArranged Output : "); | |

r.display(); | |

} | |

} |

**Output**:

Input : 1 -2 -3 -4 5 -6 7 -8 9 -10 -11 -12 20 ReArranged Output : -2 -3 -4 -6 -8 -10 -11 -12 1 5 7 9 20