DSA: Move all negative numbers to beginning and positive to end
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.
Input: -12, 11, -13, -5, 6, -7, 5, -3, -6
Output: -12 -13 -5 -7 -3 -6 11 6 5
So this question is asked in few different big tech companies and the core concept is very interesting in this question.
I will be coding in C++
Method: Two Pointer Approach
Two Pointer Approach: The idea is to solve this problem with constant space and linear time is by using a two-pointer or two-variable approach where we simply take two variables like left and right which hold the 0 and N-1 indexes. Just need to check that :
- Check If the left and right pointer elements are negative then simply increment the left pointer.
- Otherwise, if the left element is positive and the right element is negative then simply swap the elements, and simultaneously increment and decrement the left and right pointers.
- Else if the left element is positive and the right element is also positive then simply decrement the right pointer.
- Repeat the above 3 steps until the left pointer ≤ right pointer.
This is an in-place rearranging algorithm for arranging the positive and negative numbers where the order of elements is not maintained.
To maintain the Order :
To maintain the order we will traverse the array and separate all the negative elements in one single vector in order as they are in the original array and same for the positive ones. After that we will merge the two array to get a whole new array where the negative ones are coming first in order and then the positive ones.
Thanks a lot for reading till end. You can contact me in case if you need any help.👍👍👍👍👍👍