Rearrange 0s, 1s, and 2s without Sorting

Understanding the Problem

The goal is to rearrange an array containing 0s, 1s, and 2s without using any sorting algorithm.

We will explore three different methods to achieve this in Python.

Method 1: Counting Approach

This method counts the occurrences of each number and then overwrites the original array based on the counts.

def rearrange(arr):
    count0, count1, count2 = arr.count(0), arr.count(1), arr.count(2)
    arr[:count0] = [0] * count0
    arr[count0:count0+count1] = [1] * count1
    arr[count0+count1:] = [2] * count2

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

arr = [0, 1, 2, 1, 0, 2, 1, 0]
rearrange(arr)
print("Rearranged Array:")
print_array(arr)
            

Output:

0 0 0 1 1 1 2 2

Method 2: Dutch National Flag Algorithm

This method uses three pointers (low, mid, and high) to rearrange the elements efficiently.

def rearrange(arr):
    low, mid, high = 0, 0, len(arr) - 1
    while mid <= high:
        if arr[mid] == 0:
            arr[low], arr[mid] = arr[mid], arr[low]
            low += 1
            mid += 1
        elif arr[mid] == 1:
            mid += 1
        else:
            arr[mid], arr[high] = arr[high], arr[mid]
            high -= 1

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

arr = [2, 0, 2, 1, 1, 0]
rearrange(arr)
print("Rearranged Array:")
print_array(arr)
            

Output:

0 0 1 1 2 2

Method 3: Using Extra Space

This method creates a temporary array and places the elements in order.

def rearrange(arr):
    temp = [num for num in arr if num == 0] + [num for num in arr if num == 1] + [num for num in arr if num == 2]
    arr[:] = temp

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

arr = [1, 0, 2, 1, 0, 2, 1]
rearrange(arr)
print("Rearranged Array:")
print_array(arr)
            

Output:

0 0 1 1 1 2 2