Move All Negative Elements To End

In this article, we’ll discuss in-depth, how to move all negative elements to end. We’ll also discuss 2 approaches to solve the below problem. 

Problem Statement

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.

Example:

Input: 

N = 8

arr[] = {1, -1, 3, 2, -7, -5, 11, 6}

Output: 1  3  2  11  6  -1  -7  -5 

Input: 

N = 8

arr[] = {-5, 7, -3, -4, 9, 10, -1, 11}

Output : 7  9  10  11  -5  -3  -4  -1

Solution

We have an array of integers containing both positive and negative integers. We need to segregate the negative integers and put them at the end of the array. We will discuss two approaches to solve this problem.

Approach 1 (Naive solution)

A very basic approach that comes to mind to solve this problem is to use a copy array. First, traverse the array and store all the positive integers in the copy array. In the second iteration put all the negative integers in the end of the array. And now, copy the contents of the copy array to the original array. This way, we can get the negative integers seggreagated from the non-negative integers.

#include <bits/stdc++.h>
using namespace std;


/*  function to seggregate negative
    elements from the given array
    and moving them to the end  */

void segregate_elements(int n,vector<int> &arr){
    vector<int> temp;   //copy array
   
    /*  in the starting only copy the
        non-negative elements   */
    for(int i=0;i<n;i++){
        if(arr[i]>=0) temp.push_back(arr[i]);
    }
   
    /* copy the negative elements
        to the end of dummy array   */
    for(int i=0;i<n;i++){
        if(arr[i]<0) temp.push_back(arr[i]);
    }
   
    // copy the dummy array to the original array
    for(int i=0;i<n;i++){
        arr[i]=temp[i];
    }
    return;
}

int main() {
   
    //input
int n;
cin>>n;
vector<int> arr(n);
for(int i=0;i<n;i++){
    cin>>arr[i];
}

//segregating the array
segregate_elements(n,arr);

//output
for(int i=0;i<n;i++){
    cout<<arr[i]<<" ";
}
return 0;
}

Input

8
1 -1 3 2 -7 -5 11 6

Output

1 3 2 11 6 -1 -7 -5

Time complexity: O(n)

Space complexity: O(n)

Approach 2 (Two-pointer solution)

In the naive solution we were using O(n) extra space so to make it more efficient we are going to solve it in O(1) space. In this approach we maintain two pointers, low and high. The low pointer is used for iteration purpose and high pointer is used to store the position after which all the elements are negative. The implementation of this approach is given below.

#include <bits/stdc++.h>
using namespace std;


/*  function to seggregate negative
    elements from the given array
    and moving them to the end  */

void segregate_elements(int n,vector<int> &arr){
   
    int low=0,high=n-1;
   
    /*  making high point to the last
        non-negative integer in the array */
    while(arr[high]<0 && high>low){
        high--;
    }
   
    /*  swap the low integer with high
        whenever we find a negative integer */
    while(low<high){
        if(arr[low]<0){
            swap(arr[low],arr[high]);
            high--;
        }
        low++;
    }
    return;
}

int main() {
   
    //input
int n;
cin>>n;
vector<int> arr(n);
for(int i=0;i<n;i++){
    cin>>arr[i];
}

//segregating the array
segregate_elements(n,arr);

//output
for(int i=0;i<n;i++){
    cout<<arr[i]<<" ";
}
return 0;
}

Input

8
1 -1 3 2 -7 -5 11 6

Output

1 3 2 11 6 -1 -7 -5

Time complexity: O(n)

Space complexity: O(1)