Task – Move All Negative Elements to the End (Maintain Order)

Problem Statement

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

Positive elements
Negative elements

Important:
Perform the operation in-place (do not return a new array).

Example 1

Input:

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

Output:

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

Explanation:

Positive numbers remain in same order → 1, 3, 2, 11, 6
Negative numbers remain in same order → -1, -7, -5
All negatives are moved to the end
Example 2

Input:

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

Output:

[7, 9, 10, 11, -5, -3, -4, -1]
Constraints
1 ≤ arr.size ≤ 10^6
-10^9 ≤ arr[i] ≤ 10^9

Expected Time Complexity: O(n)
Expected Auxiliary Space: O(n)

Approach – Stable Separation Using Extra Space

Since we must:

Maintain order of positives
Maintain order of negatives

We cannot simply swap randomly.

Logical Steps
Traverse the array once.
Store positive elements in one list.
Store negative elements in another list.
Overwrite original array:
First all positives
Then all negatives

This keeps the order stable.

Time and Space Complexity

Time Complexity: O(n)
Space Complexity: O(n)

We use two additional lists to preserve order.

Implementation (Python)
class Solution:
def segregateElements(self, arr):
positives = []
negatives = []

    # Separate positives and negatives
    for num in arr:
        if num >= 0:
            positives.append(num)
        else:
            negatives.append(num)

    # Combine them back into original array
    index = 0

    for num in positives:
        arr[index] = num
        index += 1

    for num in negatives:
        arr[index] = num
        index += 1

Explanation of Code
We first create two lists:
positives
negatives
Traverse the array:
If number is >= 0 → add to positives
Else → add to negatives
Then rewrite the original array:
First insert all positives
Then insert all negatives

Since we modify the original array, it works in-place.

Step-by-Step Dry Run

Input:

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

After separation:

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

After rewriting array:

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