Move All Negative Elements to End

Problem Statement

Given an array arr[] containing both positive and negative integers, move all negative elements to the end of the array without changing the relative order of elements.

My Thought Process

At first, I thought this is similar to partitioning (like quicksort or two-pointer problems).

But then I noticed an important constraint:

The order of elements must not change.

This changes the entire approach.

If I try swapping elements (like placing negatives at the end using two pointers), the order of positive elements or negative elements may get disturbed.

So I needed a way to rearrange elements while keeping their original sequence intact.

Key Observation

We are not asked to sort.

We are only asked to:

• Keep all non-negative elements in the front (in the same order)


• Move all negative elements to the end (in the same order)

This means the solution must be stable.

MY way of Approach

To maintain order, I used an extra array.

Step 1: Create a temporary array

This helps us rebuild the array without disturbing order.

Step 2: Store non-negative elements first

Traverse the array and copy all elements >= 0 into the temporary array.

This ensures:

• All positive and zero values come first


• Their order remains unchanged

Step 3: Store negative elements

Traverse the array again and copy all elements < 0.

This ensures:

• All negative elements move to the end


• Their order also remains unchanged

Step 4: Copy back to original array

Finally, copy all elements from the temporary array back into the original array.

How the code Run

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



Step 1: store non-negative

[1, 3, 2, 11, 6]



Step 2: store negative

[1, 3, 2, 11, 6, -1, -7, -5]



Final Output:

[1, 3, 2, 11, 6, -1, -7, -5]

Code

class Solution {

    public void segregateElements(int[] arr) {

        int n = arr.length;

        int[] temp = new int[n];

        int index = 0;



        // Step 1: add non-negative elements

        for (int i = 0; i < n; i++) {

            if (arr[i] >= 0) {

                temp[index++] = arr[i];

            }

        }



        // Step 2: add negative elements

        for (int i = 0; i < n; i++) {

            if (arr[i] < 0) {

                temp[index++] = arr[i];

            }

        }



        // Step 3: copy back

        for (int i = 0; i < n; i++) {

            arr[i] = temp[i];

        }

    }

}

Complexity

• Time Complexity: O(n)


• Space Complexity: O(n)

Why This Works

• We are not disturbing the order of elements


• We are simply reconstructing the array in two phases


• This guarantees a stable result

Key Takeaway

Whenever a problem includes a constraint like:

“Do not change the order”

Avoid swapping-based solutions and think about stable rearrangement using extra space.