Two Pointers : Move all negative numbers to beginning and positive to end using extra space

Problem Statement:

You are given an array with +ve and -ve numbers in random order.

You need to re arrange the elements that all -ve elements appear first and then +ve elements.

Example:

Input: -10, 11, -12, -5, 6, -8, 5, -4, -6
Output: -12 -10 -5 -8 -4 -6 11 6 5

Solution 1: Using sorting

You need to sort the array of elements.

Then make sure all -ve elements will come before the +ve elements.

Time Complexity: O(nlogn)

Space Complexity: O(1)

Solution 2: Two Pointers approach

You need to initialize 2 variables, left pointer will point to left most

right pointer will point to the right most.

Repeat below steps till left is less than right:

1. While left is less than right, and value at left is negative, increment left.

2. While right is greater than left, and value at right is positive, decrement right.

3. Then when right is greater than left, swap the two values.

Time Complexity: O(n)

Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <stack>
#include <bits/stdc++.h>

using namespace std;


vector<int> solution_1 (vector<int> &arr) 
{
    sort(arr.begin(), arr.end());
    return arr;
}


vector<int> solution_2(vector<int> &arr) 
{
    
    int left = 0;
    int right = arr.size()-1;
    while (left<right) 
    {

        while (left<right && arr[left]<0) 
        {
            left++;
        }

        while (right>left && arr[right]>0) 
        {
            right--;
        }
        
        if (right>left) 
        {
            swap(arr[left], arr[right]);
            left++;
            right--;
        }
    }
    
    return arr;
}

int main() 
{
    vector<int> arr = {-10, 11, -12, -5, 6, -8, 5, -4, -6};
    vector<int> ans = solution_1(arr);
    
    for (auto num: ans) {
        cout << num << " ";
    }
    cout<<endl;
    ans = solution_2(arr);
    
    for (auto num: ans) {
        cout << num << " ";
    }
    cout<<endl;

    return 0;
}

Output

-12 -10 -8 -6 -5 -4 5 6 11 
-12 -10 -8 -6 -5 -4 5 6 11