Move All Negative Elements to End

Problem

You’re given an array of integers and need to move all negative elements to the end while maintaining the order of elements.

---

Strategy

At first, it feels like you can just swap elements in-place.

But that quickly gets messy, especially if you want to preserve the order.

Instead, I thought about it differently:
At each element, I asked—

Is it positive or negative?

So for every element:

• If it’s positive, keep it in one list
• If it’s negative, keep it in another list

This way, I can process the array in one pass and rebuild it.

---

Code

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

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

        i = 0
        for num in positives:
            arr[i] = num
            i += 1
        for num in negatives:
            arr[i] = num
            i += 1

---

Key Lines Explained

current_sum = max(arr[i], current_sum + arr[i])

This line doesn’t apply here, but the key idea is similar—making a decision at each step.

Here, the decision is simply whether the number is positive or negative.

---

Why This Works

If we try to rearrange elements directly, we might break the order.

By separating them first:

• We preserve order
• We keep the logic simple
• Then we combine them back

---

Complexity

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

---

Final Note

This problem looks like it needs tricky in-place operations, but it doesn’t.

Once you focus on separating elements instead of rearranging them during traversal, the solution becomes much simpler.