75. Sort Colors

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.

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]

Constraints: n == nums.length 1 <= n <= 300 nums[i] is either 0, 1, or 2.

Follow up: Could you come up with a one-pass algorithm using only constant extra space?

Implementation

My own solution. Complexity: O(2n)

class Solution {
    private final int RED = 0;
    private final int WHITE = 1;
    private final int BLUE = 2;

    public void sortColors(int[] nums) {
        // step 1: place all RED at the begining positions in array
        // step 2: place all BLUE at the end of array
        // after that, all WHITE elements are certainly in mid of array
        // Complexity: O(2*n)
        
        // step 1
        int l = 0; int r = nums.length-1;
        while (l < r) {
            while (l < r && nums[l] == RED) {
                l++;
            }
            while (l < r && nums[r] != RED) {
                r--;
            }

            if (l < r) {
                // swap
                nums[r] = nums[l];
                nums[l] = RED;
            } else {
                break; // important, to prevent increase left pointer when we have found all RED element;
            }

            l++; r--;
        }

        // step 2
        r = nums.length-1; // reset right pointer, not left pointer since left pointer passed all RED elements
        while (l < r) {
            while (l < r && nums[r] == BLUE) {
                r--;
            }
            while (l < r && nums[l] != BLUE) {
                l++;
            }

            if (l < r) {
                // swap
                nums[l] = nums[r];
                nums[r] = BLUE;
            }

            l++; r--;
        }
    }
}

Other solution that use one-pass loop. Complexity: only O(n)

class Solution {
    private final int RED = 0;
    private final int WHITE = 1;
    private final int BLUE = 2;
    private int[] nums;

    public void sortColors(int[] nums) {
        this.nums = nums;
        int left = 0; int mid = 0; int right = nums.length-1;

        while (mid <= right) {
            if (nums[mid] == WHITE) {
                mid++;
            } else if (nums[mid] == RED) {
                swap(mid, left);
                mid++;
                left++;
            } else {
                swap(mid, right);
                right--;
            }
        }
    }

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

And you can check this solution at: Leetcode discussion or here

Intuition

The problem requires us to sort an array of integers representing colors in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue. We are given that the colors red, white, and blue are represented by the integers 0, 1, and 2 respectively.

Approach : Dutch National Flag algorithm

• The Dutch National Flag algorithm, also known as 3-way partitioning, is an algorithm for sorting an array containing three distinct values. The algorithm was designed to solve the problem of sorting an array containing only 0s, 1s, and 2s, which is similar to the problem in the given question.

• The algorithm works by maintaining three pointers: low, mid, and high. The low pointer points to the beginning of the array, the high pointer points to the end of the array, and the mid pointer starts at the beginning of the array and moves through it.

• The idea behind the algorithm is to keep all the 0s before the low pointer, all the 2s after the high pointer, and all the 1s between the low and high pointers. The algorithm moves the mid pointer through the array, comparing the value at each position with 1. If the value is 0, the element is swapped with the element at the low pointer, and the low and mid pointers are incremented. If the value is 2, the element is swapped with the element at the high pointer, and the high pointer is decremented. If the value is 1, the mid pointer is simply incremented.

• The algorithm terminates when the mid pointer crosses the high pointer, indicating that all the elements have been processed and the array is sorted.