Java: Sort Colors (Dutch National Flag Problem)

Thought Process

The Sort Colors problem (also known as the Dutch National Flag Problem) requires sorting an array of 0s, 1s, and 2s in-place. Here are two approaches:

Approach 1: Two-Pointer Technique - Use two pointers, start and end, to track the boundaries of 0s and 2s. Iterate through the array with a third pointer, ptr. If nums[ptr]=0, swap it with nums[start] and move both start and ptr forward. If nums[ptr]=2, swap it with nums[end] and move end backward. If nums[ptr]=1, simply move ptr forward.

Approach 2: Counting and Overwriting - Use three counters (n0, n1, n2) to count the occurrences of 0s, 1s, and 2s. Overwrite the array based on the counts, ensuring all 0s come first, followed by 1s, and then 2s.

Approach 1: Two-Pointer Technique 

class Solution {
    public void sortColors(int[] nums) {
        int start = 0;
        int end = nums.length - 1;
        int i = 0;
  
        while (start <= end) {
          // Put 0 at the starting of array.  
          if (nums[start] == 0) {
                swap(nums, start, i);
                start++;
                i++;
            }
            // Put 2 at the end of array. 
            else if (nums[start] == 2) {
                swap(nums, start, end);
                end--;
            } else
                start++;
        }
    }
  
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

Approach 2: Counting and Overwriting 

class Solution {
    public void sortColors(int[] nums) {
          
        int n0 = -1;
        int n1 = -1;
        int n2 = -1;
  
        for(int i=0;i<nums.length;i++){
  
            if(nums[i]==2){
                nums[++n2] = 2;
            }
            else if(nums[i]==1){
                nums[++n2] = 2;
                nums[++n1] = 1;
            }
            else{
                nums[++n2] = 2;
                nums[++n1] = 1;
                nums[++n0] = 0;
            }
        }
    }
}

Code Complexity

Time Complexity: O(n)

Both approaches iterate through the array once, ensuring linear time complexity.

Space Complexity: O(1)

Both approaches use constant extra space, making them highly efficient.

Code copied!