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 Java.

Method 1: Counting Approach

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

public class RearrangeArray {
    public static void rearrange(int[] arr) {
        int count0 = 0, count1 = 0, count2 = 0;
        for (int num : arr) {
            if (num == 0) count0++;
            else if (num == 1) count1++;
            else count2++;
        }
        int index = 0;
        while (count0-- > 0) arr[index++] = 0;
        while (count1-- > 0) arr[index++] = 1;
        while (count2-- > 0) arr[index++] = 2;
    }
    
    public static void printArray(int[] arr) {
        for (int num : arr) System.out.print(num + " ");
        System.out.println();
    }
    
    public static void main(String[] args) {
        int[] arr = {0, 1, 2, 1, 0, 2, 1, 0};
        rearrange(arr);
        System.out.println("Rearranged Array:");
        printArray(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.

public class RearrangeArray {
    public static void rearrange(int[] arr) {
        int low = 0, mid = 0, high = arr.length - 1;
        while (mid <= high) {
            if (arr[mid] == 0) {
                int temp = arr[low]; arr[low] = arr[mid]; arr[mid] = temp;
                low++; mid++;
            } else if (arr[mid] == 1) {
                mid++;
            } else {
                int temp = arr[mid]; arr[mid] = arr[high]; arr[high] = temp;
                high--;
            }
        }
    }
    
    public static void printArray(int[] arr) {
        for (int num : arr) System.out.print(num + " ");
        System.out.println();
    }
    
    public static void main(String[] args) {
        int[] arr = {2, 0, 2, 1, 1, 0};
        rearrange(arr);
        System.out.println("Rearranged Array:");
        printArray(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.

public class RearrangeArray {
    public static void rearrange(int[] arr) {
        int[] temp = new int[arr.length];
        int index = 0;
        for (int num : arr) if (num == 0) temp[index++] = 0;
        for (int num : arr) if (num == 1) temp[index++] = 1;
        for (int num : arr) if (num == 2) temp[index++] = 2;
        System.arraycopy(temp, 0, arr, 0, arr.length);
    }
    
    public static void printArray(int[] arr) {
        for (int num : arr) System.out.print(num + " ");
        System.out.println();
    }
    
    public static void main(String[] args) {
        int[] arr = {1, 0, 2, 1, 0, 2, 1};
        rearrange(arr);
        System.out.println("Rearranged Array:");
        printArray(arr);
    }
}
            

Output:

0 0 1 1 1 2 2