Given an array which consists of only 0, 1 and 2. Sort the array without using any sorting algo

Problem Statement

Given an array consisting of only 0s, 1s, and 2s, sort the array in-place without using any sorting algorithm. This is also known as the Dutch National Flag Problem.

Example:

• Input: [0, 1, 2, 0, 1, 2, 1, 0]
• Output: [0, 0, 0, 1, 1, 1, 2, 2]

Approach 1: Counting Sort (Two Pass)

Intuition

Since there are only three distinct values, count the occurrences of each and overwrite the array.

Algorithm

1. Count occurrences of 0s, 1s, and 2s
2. Overwrite the array: first count0 zeros, then count1 ones, then count2 twos

public class Solution {
    public void sortColors(int[] nums) {
        int count0 = 0, count1 = 0, count2 = 0;
        
        // First pass: count occurrences
        for (int num : nums) {
            if (num == 0) count0++;
            else if (num == 1) count1++;
            else count2++;
        }
        
        // Second pass: overwrite array
        int index = 0;
        while (count0-- > 0) nums[index++] = 0;
        while (count1-- > 0) nums[index++] = 1;
        while (count2-- > 0) nums[index++] = 2;
    }
}

Complexity Analysis

• Time Complexity: O(n) - Two passes through the array
• Space Complexity: O(1) - Only three counter variables

Approach 2: Dutch National Flag Algorithm (Optimal - Single Pass)

Intuition

Use three pointers to partition the array into three sections:

• [0...low-1] contains 0s
• [low...mid-1] contains 1s
• [high+1...n-1] contains 2s
• [mid...high] is the unsorted region

Algorithm

1. Initialize low = 0, mid = 0, high = n-1
2. Traverse while mid <= high:
   • If arr[mid] == 0: swap with arr[low], increment both low and mid
   • If arr[mid] == 1: just increment mid
   • If arr[mid] == 2: swap with arr[high], decrement high (don't increment mid)

public class Solution {
    public void sortColors(int[] nums) {
        int low = 0, mid = 0, high = nums.length - 1;
        
        while (mid <= high) {
            if (nums[mid] == 0) {
                // Swap nums[low] and nums[mid]
                int temp = nums[low];
                nums[low] = nums[mid];
                nums[mid] = temp;
                low++;
                mid++;
            } else if (nums[mid] == 1) {
                mid++;
            } else { // nums[mid] == 2
                // Swap nums[mid] and nums[high]
                int temp = nums[mid];
                nums[mid] = nums[high];
                nums[high] = temp;
                high--;
                // Don't increment mid here
            }
        }
    }
}

Dry Run Example

Complexity Analysis

• Time Complexity: O(n) - Single pass through the array
• Space Complexity: O(1) - Only three pointer variables

Why Not Increment mid When Swapping with high?

When we swap nums[mid] with nums[high], the element that comes to mid position could be:

• 0 (needs to go to the beginning)
• 1 (in correct position)
• 2 (needs to go to the end again)

So we must check this new element before moving forward. However, when swapping with low, the element coming to mid must be 1 (since everything before low is already processed), so we can safely increment mid.

Key Takeaways

1. Dutch National Flag algorithm is a classic three-way partitioning technique
2. Single pass O(n) solution using three pointers is optimal
3. The key insight is maintaining invariants for three sections
4. This technique extends to partitioning around a pivot (useful in QuickSort variants)
5. The algorithm is in-place and stable for 0s and 2s relative to each other