CA 09 - Move all negative elements to the end

Problem Statement

Given an unsorted array arr[] having both negative and positive integers. The task is to place all negative elements at the end of the array without changing the order of positive elements and negative elements.

Note: Don't return any array, just do in-place on the array.

Examples:

Input: arr[] = [1, -1, 3, 2, -7, -5, 11, 6]
Output: [1, 3, 2, 11, 6, -1, -7, -5]
Explanation: By doing operations we separated the integers without changing the order.

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

My Goal

For this problem, my goal was to:

Maintain the order of elements (stable arrangement)
Separate positive and negative numbers efficiently
Solve the problem in linear time
Keep the logic simple and readable

Solution

For this problem, my goal was to keep the order of elements the same while separating positive and negative numbers efficiently. I also wanted to solve it in linear time without making the logic complicated, so the approach stays simple and easy to understand.

I used a two-list approach since it’s very straightforward. I just loop through the array once and store all positive numbers in one list and all negative numbers in another list. After that, I combine both lists back together, keeping positives first and negatives after. This way, the original order of elements is preserved within each group.

While iterating through the array, each element is checked and added to either the positive list or the negative list based on its value. Once the loop is done, I merge both lists to form the final result. This approach works in linear time and keeps the code clean and readable.

Solution Code (Python)

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

p = []
n = []

for x in a:
    if x >= 0:
        p.append(x)
    else:
        n.append(x)

a = p + n

print(a)