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)**.