Move all negative numbers to the beginning and positives to end, maintaining their order
An array contains both positive and negative numbers in random order. Rearrange the array elements so that all negative numbers appear before all positive numbers and the order of their occurrence in the given array should be maintained(order of negatives among negatives and positives among positives).
Input: [3, 5, -9, -8, 1 , 2, -10, -11, 15, 20, -20, 22]
Output: [-9, -8, -10, -11, -20, 3, 5, 1, 2, 15, 20, 22]
NOTE: Order of elements is important here.
My Approach(without using extra space):
- The idea is to solve the problem by dividing the array into four parts at each step when we want to shift the elements while iterating the array ( shifting condition will be arr[index]<0).
-
Steps:
- iterate through the list
- At every step, when a negative number encountered, slice the array in four parts say
- first part: the part with the negatives.
- the mid part: which we have to shift after the encountered negative number
- the -ive number.
- the last part, which is not iterated.
CODE:
let a = [3, 5, -9, -8, 1 , 2, -10, -11, 15, 20, -20, 22];
var nIndex = 0;
for(var index = 0; index < a.length ; index++){
if(a[index]<0){
//negatives array
let negativesArray= a.slice(0, nIndex);
let midArray = a.slice(nIndex, index);
let neg_num = a[index];
let endArray = a.slice(index+1);
a= [...negativesArray, neg_num,...midArray,...endArray];
nIndex++;
}
}
console.log(a) //output: [-9, -8, -10, -11, -20, 3, 5, 1, 2, 15, 20, 22]
Let's discuss your approach in the discussion box or you can hit me up at aastha.talwaria29@gmail.com.
Thanks for reading.
Top comments (2)
Just typed on my phone so I haven't checked it works, but could you do something like this?
Yes, this will also work. But, I was trying not to use extra space.