Move All Negative Elements to the End of an Array

Introduction

In array-based problems, rearranging elements based on certain conditions is a common task. One such problem is moving all negative numbers to the end of the array while maintaining the relative order of elements.

This type of problem helps in understanding array traversal and stable rearrangement techniques.

Problem Statement

Given an unsorted array containing both positive and negative integers, rearrange the array such that:

• All positive elements appear first
• All negative elements are moved to the end
• The *relative order of elements is preserved

Example 1

Input:

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

Output:

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

Explanation:
All positive numbers are moved to the front, and negative numbers are placed at the end without changing their original order.

Example 2

Input:

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

Output:

[7, 9, 10, 11, -5, -3, -4, -1]

Approach: Using Extra List (Simple Method)

• Traverse the array
• Store positive numbers in one list
• Store negative numbers in another list
• Combine both lists

Python Implementation

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

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

    return positives + negatives

# Example usage
arr = [1, -1, 3, 2, -7, -5, 11, 6]
print(move_negatives(arr))

Approach 2: In-Place Method (Without Extra Space)**

• Traverse the array
• Whenever a positive element is found, move it forward
• Maintain order using shifting

Python Implementation (In-Place)

def move_negatives(arr):
    j = 0  # position for next positive number

    for i in range(len(arr)):
        if arr[i] >= 0:
            # Shift elements to maintain order
            temp = arr[i]
            k = i
            while k > j:
                arr[k] = arr[k - 1]
                k -= 1
            arr[j] = temp
            j += 1

    return arr

# Example usage
arr = [1, -1, 3, 2, -7, -5, 11, 6]
print(move_negatives(arr))

Conclusion

Moving negative elements to the end of an array is a classic problem that demonstrates how to rearrange data while maintaining order. Choosing between space and time efficiency depends on the requirements of the problem.

This concept is useful in many real-world scenarios where data needs to be filtered and rearranged efficiently.