Move All the Negative Elements to One Side of the Array

Understanding the Problem

The goal is to move all negative elements to one side of the array using different methods.

Method 1: Using Two Pointers

This method uses two pointers to swap negative and positive elements efficiently.

def rearrange(arr):
    left, right = 0, len(arr) - 1
    while left <= right:
        if arr[left] < 0:
            left += 1
        elif arr[right] >= 0:
            right -= 1
        else:
            arr[left], arr[right] = arr[right], arr[left]
            left += 1
            right -= 1

def print_array(arr):
    print(" ".join(map(str, arr)))

arr = [-12, 11, -13, -5, 6, -7, 5, -3, -6]
rearrange(arr)
print_array(arr)
            

Output:

-12 -13 -5 -7 -3 -6 6 5 11

Method 2: Using Partition Process of QuickSort

This method places all negative elements before positive elements using partitioning.

def partition(arr):
    j = 0
    for i in range(len(arr)):
        if arr[i] < 0:
            arr[i], arr[j] = arr[j], arr[i]
            j += 1

def print_array(arr):
    print(" ".join(map(str, arr)))

arr = [-12, 11, -13, -5, 6, -7, 5, -3, -6]
partition(arr)
print_array(arr)
            

Output:

-12 -13 -5 -7 -3 -6 6 5 11

Method 3: Using Extra Space

This method creates a new array and stores negative and positive elements separately.

def rearrange_with_extra_space(arr):
    temp = [num for num in arr if num < 0] + [num for num in arr if num >= 0]
    for i in range(len(arr)):
        arr[i] = temp[i]

def print_array(arr):
    print(" ".join(map(str, arr)))

arr = [-12, 11, -13, -5, 6, -7, 5, -3, -6]
rearrange_with_extra_space(arr)
print_array(arr)
            

Output:

-12 -13 -5 -7 -3 -6 6 5 11