75. Sort Colors 🔥

Medium

Problem:

Considering the color red as 0, white as 1, and blue as 2, perform an in-place sorting in the order.

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]

https://leetcode.com/problems/sort-colors/

What to learn:

This problem is identical to the Dutch National Flag Problem proposed by Dijkstra in 1976 and is closely related to the idea of improving quicksort.

The idea was to use a pivot to divide into three parts: the smaller part, the equal part, and the larger part (Three-way partitioning), aiming to enhance the conventional two-part division of quicksort.

three-way-partition(A : array of values, mid : value):
    i ← 0
    j ← 0
    k ← size of A - 1

    while j <= k:
        if A[j] < mid:
            swap A[i] and A[j]
            i ← i + 1
            j ← j + 1
        else if A[j] > mid:
            swap A[j] and A[k]
            k ← k - 1
        else:
            j ← j + 1

This pseudocode uses i and k as pointers on both sides, with j moving and swapping based on the mid value.

Pseudocode: https://en.wikipedia.org/wiki/Dutch_national_flag_problem

Solution:

When the comparison is finally complete, red points to one position beyond the index smaller than 1, blue points to the initial spot of the index larger than 1, and the comparison concludes as white and blue overlap.

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        red, white, blue = 0, 0, len(nums)
        while white < blue:
            if nums[white] < 1:
                nums[red], nums[white] = nums[white], nums[red]
                white += 1
                red += 1
            elif nums[white] > 1:
                blue -= 1
                nums[white], nums[blue] = nums[blue], nums[white]
            else:
                white += 1

Example run with nums = [2,0,2,1,1,0]

Initial:
red = 0, white = 0, blue = 6, nums = [2,0,2,1,1,0]

1st iteration:
nums[white] = 2, which is > 1
So, decrement blue by 1 and swap nums[white] and nums[blue]: nums = [0,0,2,1,1,2], red = 0, white = 0, blue = 5

2nd iteration:
nums[white] = 0, which is < 1
So, increment both red and white: nums = [0,0,2,1,1,2], red = 1, white = 1, blue = 5

3rd iteration:
nums[white] = 0, which is < 1
Increment both red and white: nums = [0,0,2,1,1,2], red = 2, white = 2, blue = 5

4th iteration:
nums[white] = 2, which is > 1
Decrement blue by 1 and swap nums[white] and nums[blue]: nums = [0,0,1,1,2,2], red = 2, white = 2, blue = 4

5th iteration:
nums[white] = 1, which is neither > 1 nor < 1
So, increment white: red = 2, white = 3, blue = 4

6th iteration:
nums[white] = 1, which is neither > 1 nor < 1
Increment white: red = 2, white = 4, blue = 4

Since white is now not less than blue, the loop ends, and nums = [0,0,1,1,2,2] is sorted in place.