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]