Segregate Positive and Negative Numbers in an Array Without Changing Order

When working with arrays, a common problem is rearranging elements based on a condition while preserving their original order. In this post, we will solve the problem of moving all negative numbers in an array to the end without disturbing the order of positive and negative numbers.

Problem Statement

Given an array of integers, rearrange it so that all non-negative elements appear first, followed by negative elements. The relative order of elements must remain unchanged.

Example 1:

Input:

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

Output:

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

Example 2:

Input:

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

Output:

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

Constraints:

1 ≤ array size ≤ 10⁶

-10⁹ ≤ arr[i] ≤ 10⁹

Expected Time Complexity: O(n)

Expected Auxiliary Space: O(n)

Approach

To solve this efficiently:

Traverse the array once and store all non-negative elements in one temporary list.

Store all negative elements in another temporary list.

Merge both lists back into the original array.

This approach ensures:

The order of elements is preserved (stable rearrangement).

Time complexity is linear, O(n).

Auxiliary space is O(n), which is acceptable according to the problem constraints.

Python Implementation Code

class Solution:

def segregateElements(self, arr):

pos = []

neg = []

    # Separate positive and negative elements

    for i in arr:

        if i >= 0:

            pos.append(i)

        else:

            neg.append(i)



    # Merge back into original array

    i = 0

    for x in pos:

        arr[i] = x

        i += 1



    for x in neg:

        arr[i] = x

        i += 1

How It Works

Take input array:

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

Separate into two lists:

pos = [1, 3, 2, 11, 6]

neg = [-1, -7, -5]

Merge back into original array:

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

Order of positive and negative elements is preserved.

Complexity Analysis

Time Complexity: O(n) → One pass to separate + one pass to merge

Space Complexity: O(n) → Two auxiliary lists

Conclusion

This problem highlights the importance of stable rearrangement of elements in an array. Using a simple auxiliary list approach, we can efficiently move all negative numbers to the end without disturbing the original order of elements.