Home » Data Structure » Array Data Structure

Move all negative elements to end in order with extra space allowed

C++ implementation to move all negative elements to end in order with extra space allowed.
Submitted by Vikneshwar GK, on March 20, 2022

Consider an unsorted integer array, of size n, which contains both positive and numbers. The task at hand is to move all the negative elements to the end of the array without changing the order of positive and negative elements present in the array.

Example:

Input:
array[]= {5, 1, -2, 3, -6, -7 , 9, 10}

Output:
array[] = {5, 1, 3, 9, 10, -2, -6, -7} 

Input:
array[] = {1, -2, 3, -4, 5, -6}

Output:
array[] = {1, 3, 5, -2, -4, -6}

Solution:

This method involves using an auxiliary array and two pointers to place the negative and positive elements in their corresponding position. It involves the following steps:

Set pos = 0 and neg = n-1 where n is the length of the array.
Initialize a temporary array of size n.
Iterate through the original array and check if the element from last is negative, if yes, place them in neg position and decrement it.
Iterate through the original array and check if the element from first is positive, if yes, place them in pos position and increment it.
Print the temporary array.

C++ Implementation:

#include <iostream>
using namespace std;

// Function to print the array
void printArray(int array[], int length)
{
    for (int i = 0; i < length; i++) {
        cout << array[i] << " ";
    }
}

// Function to move the negative elements to the end
void rearrangeArray(int array[], int length)
{
    int temp[length], pos = 0, neg = length - 1;

    for (int i = 0; i < length; i++) {
        if (array[length - 1 - i] < 0) {
            temp[neg--] = array[length - 1 - i];
        }
        if (array[i] >= 0) {
            temp[pos++] = array[i];
        }
    }
    printArray(temp, length);
}

// Main function
int main()
{
    int array[100];
    int N;
    
    cout << "Enter Number of elements: ";
    cin >> N;

    for (int i = 0; i < N; i++) {
        cout << "Enter element " << i + 1 << ": ";
        cin >> array[i];
    }

    rearrangeArray(array, N);
    
    return 0;
}

Output:

Enter Number of elements: 8
Enter element 1: 1
Enter element 2: -1
Enter element 3: -3
Enter element 4: -2
Enter element 5: 7
Enter element 6: 5
Enter element 7: 11
Enter element 8: 6
1 7 5 11 6 -1 -3 -2

Time Complexity: O(n), where n is the length of the array.