Extract Negative and Positive Numbers in constant space

Given an array of integers containing negative and positive numbers. Our task is to extract negative and positive numbers aside.

Let’s try to understand the problem clearly with the help of an example.

Let’s say given an array:

arr = {-1,2,-3,5,6,-12}

And we need to make it:

either : {-1,-3,-12,2,5,6} or {-3,-1,-12,5,2,6}. By multiple options I mean that the order of numbers don’t matter. What matter is the negative numbers need to be one side and the positive numbers need to be one side.

Enough with question. Now let’s move on to the solution we are supposed to take.

Approach 1: Quicksort Partition Method

This approach is actually the partition method of quicksort which we use with a special case that here the pivot we consider is 0 i.e all the elements less than 0 reside one side and all the elements greater than zero reside on the other side. And this is exactly what our requirement was. Well enough with explanation, now we will write code and the code will speak the rest logic

Quicksort partition

Time complexity : O(n)

Space complexity: O(1)

Approach 2: Two Pointer method

Let us first try to understand the intuition behind this method then we will proceed with the code.

The whole idea of this method is keep the negative number as left as possible and keep the positive number as right as possible.

Let’s try to understand the concept with he help of this example.

img 1

I hope things would have got more clearer viewing this example. Being done with this let us now have a look at the code.

Time complexity O(n)

Space Complexity: O(1)