Problem

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library’s sort function.

By the way this is Dutch National Flag - 🇳🇱.

Examples

Example 1:

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Example 2:

Input: nums = [2,0,1]
Output: [0,1,2]

Solution

The Dutch National Flag Algorithm sorts an array of red, blue, and white objects by separating them from each other based on their colors. Hence, we can adopt the algorithm to sort any array of three different kinds of objects / values.

Method 1 - Using 3-Way Partition Quicksort

3 way quick sort basically partitions the array in 3 parts:

  1. First part is lesser than the pivot - arr[l..i]
  2. Second part is equal to pivot - arr[i+1..j-1]
  3. Third part is greater than pivot - arr[j..r]

Algorithm

l, r, and m are pointers used to separate the 0s, 1s, and 2s. 

l (left) marks the end of the zone for 0s, m (middle) is the current index being checked, and r (right) marks the start of the zone for 2s.

Lets assume l is the left pointer, covering the 0s, r is the right pointer covering 2s and m is somewhere in the middle covering 1s.

  1. Start with l=0, m=0 and r = n - 1, where n is length of array.
  2. If the current element nums[m] is 0, it should be at the start of the array. We swap the current element with the element at the l pointer and then increase both m and l pointers. This is safe because anything on the left of m is already processed and confirmed not to be 2.
  3. If the current element nums[m] is 2, it should be at the end of the array. We swap the current element with the element at the r pointer. Then we only decrement the r pointer as the element at m could be 0 and might need to be swapped with the element at l. Here, we do not immediately increment m because the newly swapped element from position r hasn’t been processed yet.
  4. If the current element nums[m] is 1, then we just increment m, value is at correct place

Here is the video explanation:

Code

Java
class Solution {

	public void sortColors(int[] nums) {
		int l = 0; //left
		int r = nums.length - 1; // right
		int m = 0; //mid
		while (m <= r) {
			if (nums[m] == 0) {
				swap(nums, m, l);
				l++;
			} else if (nums[m] == 2) {
				swap(nums, m, r);
				r--;
				// may have swapped an extra 0 from the end of array that requires extra processing, so decrement index to account for it
				// as middle shouldn't increase
				m--;
			}
			// Now nums[m] = 1
			m++;
		}
	}

	private void swap(int[] A, int i, int j) {
		int tmp = A[i];
		A[i] = A[j];
		A[j] = tmp;
	}
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)

Dry Run

nums = [ 2, 0, 2, 1, 1, 0]
        ↑ ↑             ↑
        l m             r
l = 0
m = 0
r = 5 (length of nums - 1)

Iteration 1

nums = [ 0, 0, 2, 1, 1, 2]
        ↑ ↑             ↑
        l m             r
nums[m] = nums[0] = 2
Swap nums[m] with nums[r]: nums = [0, 0, 2, 1, 1, 2]
Decrement r: r = 4
m stays 0 because it was decremented after swap
nums = [ 0, 0, 2, 1, 1, 2]
        ↑ ↑          ↑
        l m          r

Iteration 2

nums = [ 0, 0, 2, 1, 1, 2]
        ↑ ↑          ↑
        l m          r
nums[m] = nums[0] = 0
Swap nums[m] with nums[l]: nums = [0, 0, 2, 1, 1, 2]
Increment l: l = 1
Increment m: m = 1

nums = [0,  0, 2, 1, 1, 2]
           ↑ ↑       ↑
           l m       r

and so on.

Method 2 - Partition by Checking Low and High Values

This is similar to previous problem, but this will work for any 3 different numbers. In this problem, we know low=0 and high=, but if we don’t, this algorithm will help us out.

Code

Java
public void sortColors(int[] nums) {
	dutchFlagSort(nums, 0, 2);
}
private void dutchFlagSort(int nums[], int low, int high) {
    if (nums.length == 0) {
	    return;
    }

    int l = 0;
    while (nums[l] == low && l < arraySize) {
	    l++;
    }
        
    int r = nums.length - 1;
    while (nums[r] == high && r >= 0) {
	    r--;
    }
        

    int temp = 0;
    int pivot;
    for (pivot = l; pivot <= r;) {
        if (nums[pivot] == low) {
            temp = nums[pivot];
            nums[pivot] = nums[l];
            nums[l] = temp;
            pivot++;
            l++;
        } else if (nums[pivot] == high) {
            temp = nums[pivot];
            nums[pivot] = nums[r];
            nums[r] = temp;
            upper--;
        } else {
            pivot++;
        }
    }
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)

Method 3 - Using 2 Pass Counting Sort

Code

Java
	// 2-pass
public void sortColors(int[] nums) {
	int count0 = 0, count1 = 0, count2 = 0;
	for (int i = 0; i<nums.length; i++) {
		if (nums[i] == 0) {
			count0++;
		}
		if (nums[i] == 1) {
			count1++;
		}
		if (nums[i] == 2) {
			count2++;
		}
	}
	for (int i = 0; i<nums.length; i++) {
		if (i<count0) {
			nums[i] = 0;
		} else if (i<count0 + count1) {
			nums[i] = 1;
		} else {
			nums[i] = 2;
		}
	}
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)