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.

---