An array A is given, A contains both positive and negative numbers in random order. The task is to rearrange the array elements so that all negative numbers appear before all positive numbers.
Example 1: Rearrange (-)ve elements to the left in : {1, -2, 3, -4, 5, -6, 7}
Input: {1, -2, 3, -4, 5, -6, 7}
Output: {-6,-2,-4,5,3,7,1}
Example 2: Rearrange (-)ve elements to the left in : {23, -12, 4, 74, -1, 9, -45}
Input: {23, -12, 4, 74, -1, 9, -45}
Output: {-45,-12,-1,74,9,4,23}
Solutions
Method 1: Dutch National Flag algorithm
In this approach we will use famous Dutch National Flag algorithm. The idea is to divide the array in two parts such that; [1 to low-1] will have (-)ve values, [low to high-1] will have mixed elements and [high to n] will have (+)ve elements.
Start with low=0, high=n-1 and traverse the array until low < high; if arr[low] < 0 increment low (low++) else swap arr[low] & arr[high] and decrement high (high--).
Complexity
The time complexity of this solution is O(n) and space complexity is O(1).