Given an array of integers which might contain both positive and negative integers, how do you modify the array such that all the positive and all the negative elements appear together.
For example consider the following array.
[36, -2, -18, 24, 42, -3, 6]
This should be transformed to some thing like
[-2, -18, -3, 24, 42, 36,6]
Here is the simple algorithm for this which runs in O(n) time and constant space.
- Maintain an index for storing the negative elements (nIndex) and initialize it with zero.
- Iterate through all the elements and if any of them is negative, swap it with the element at negative elements index (nIndex).
Here is the C++ implementation for this.