Segregate Positive and Negative Numbers in an Array Without Changing Order

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
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.

Python 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

steps
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.

Conclusion

we can able move all negative numbers to the end without disturbing the original order of elements.