Move all negative elements to end

Introduction

In many real-world problems, we need to rearrange elements based on conditions while maintaining their original order.

This problem focuses on moving all negative numbers to the end of the array while keeping the order of both positive and negative elements unchanged.

Problem Statement

Given an unsorted array arr[] containing both positive and negative integers:

1. Move all negative elements to the end
2. Maintain the original order of:

• Positive elements
• Negative elements

1. Do it in-place (no return needed)

Examples

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]

Intuition

We need to:

• Keep positive numbers in front (same order)
• Push negative numbers to end (same order)

This means we need a stable arrangement (order should not change).

Approach

Since order must be preserved, the best clean approach is:

1. Create a temporary list
2. First add all positive elements
3. Then add all negative elements
4. Copy back to original array

Code (Python)

def move_negatives(arr):
    temp = []

    # Add positive elements
    for num in arr:
        if num >= 0:
            temp.append(num)

    # Add negative elements
    for num in arr:
        if num < 0:
            temp.append(num)

    # Copy back to original array
    for i in range(len(arr)):
        arr[i] = temp[i]

Step-by-Step Idea

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

• First pass → [1, 3, 2, 11, 6]
• Second pass → [-1, -7, -5]
• Final → [1, 3, 2, 11, 6, -1, -7, -5]

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

Conclusion

This problem teaches an important concept: rearranging elements while preserving order.