Take an example, given [1, 7, -5, 9, -12, 15]
The answer would be: [-5, -12, 1, 7, 9, 15]
Proceed with following steps :
- Walk through the array and count negative numbers - O(n)
- Create a new array of size O(n)
- Walk through original array and place numbers into the new array. Use the known number of negative numbers to offset the positive ones - O(n)
Option B should be Correct.
or
a quick way to do it in Python. It slightly differs from the above in first creating an array for the negatives, then appending the positives. So it's not as efficient, but still O(n).
>>> a = [1,7,-5,9,-12,15]
>>> print [x for x in a if x < 0] + [y for y in a if y >= 0]
[-5, -12, 1, 7, 9, 15]
