Move Negative Elements to End While Maintaining Order

Source: Dev.to

Problem Statement

Given an unsorted array containing both positive and negative integers, rearrange the array such that all negative elements are moved to the end without changing the relative order of the positive and negative elements.

Example

Input:

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

Output:

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

Approach

1. Iterate through the array once.
2. Collect positive (or zero) numbers in one list.
3. Collect negative numbers in another list.
4. Concatenate the two lists and overwrite the original array.

Code

def rearrange(arr):
    positives = []
    negatives = []

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

    arr[:] = positives + negatives

Explanation

• The method preserves the original order because elements are appended to the positives and negatives lists in the order they appear.
• After processing, the positives list is placed first, followed by the negatives list, achieving the required arrangement.

Time Complexity

• O(n) – the array is traversed only once.

Space Complexity

• O(n) – additional space is used for the two auxiliary lists.