Sorting an Array of 0s, 1s, and 2s

Problem Statement

Given an array of integers where each element is either 0, 1, or 2, sort the array in a way that all 0s come first, followed by all 1s, and then all 2s.

For example, given the array {0, 1, 2, 0, 1, 2}, the sorted array should be {0, 0, 1, 1, 2, 2}.

Dutch National Flag Algorithm

The Dutch National Flag algorithm, also known as three-way partitioning, is a simple and efficient method to solve this problem. The algorithm is based on a three-way partitioning strategy known from the Dutch National Flag problem (hence the name).

The main idea of the algorithm is to maintain three pointers low, mid and high:

• low is for 0
• mid is for 1
• high is for 2

The algorithm processes all elements in the array and moves the 0s to the beginning, the 2s to the end, and leaves the 1s in the middle. Here’s how it works:

1. Initialize low and mid to the start of the array and high to the end of the array.
2. Iterate over the array. If the current element (nums[mid]) is:
   • 0: swap it with nums[low] and increment both low and mid. This is because we know that all elements before mid are already sorted, so after the swap, nums[mid] is guaranteed to be 1, and we can safely increment mid.
   • 1: just increment mid. This is because we’re just expanding the section of 1s in our array.
   • 2: swap it with nums[high] and decrement high, but leave mid where it is. This is because the new value of nums[mid] after the swap is unknown, and we need to process it on the next iteration.

By doing this, all 0s will end up before low, all 2s will be after high, and all 1s will be between low and high, effectively sorting the array.

Here’s the Java code for this algorithm:

class Solution {
    public void sortColors(int[] nums) {
        int low = 0, mid = 0, high = nums.length - 1;
        while (mid <= high) {
            switch (nums[mid]) {
                case 0:
                    swap(nums, low++, mid++);
                    break;
                case 1:
                    mid++;
                    break;
                case 2:
                    swap(nums, mid, high--);
                    break;
            }
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

Time Complexity: The time complexity of this algorithm is O(n), where n is the length of the input array. This is because we are processing each element of the array exactly once.

Space Complexity: The space complexity is O(1), as no extra space is required.

In conclusion, the Dutch National Flag algorithm provides an efficient solution to the problem of sorting an array of 0s, 1s, and 2s. It’s simple, easy to understand, and runs in linear time. I hope this blog post helps you understand this algorithm better! 😊