Sort Colors

How it works

This is a streamlined version of the previous approach. We iterate with pointer two and always write 2 at the current position. If the original value was less than 2, we also write 1 at position one. If it was less than 1 (i.e., 0), we also write 0 at position zero. This cascading write pattern ensures correct placement.

Steps

1. Initialize pointers zero and one at 0.
2. Iterate through the array with pointer two:
   • Save the current value, then set nums[two] = 2.
   • If the saved value was less than 2, set nums[one] = 1 and increment one.
   • If the saved value was less than 1, set nums[zero] = 0 and increment zero.

Complexity

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

Things to watch for

Incrementing the Current Pointer After Swapping with the Right Boundary

In the Dutch National Flag algorithm, when you swap the current element with the right boundary (for value 2), you must not increment the current pointer. The swapped element from the right has not been examined yet and could be 0, 1, or 2.

Using Strict Less Than Instead of Less Than or Equal

The loop condition must be i <= r not i < r. Using strict less than causes the algorithm to miss processing the element at position r when i equals r, potentially leaving an unsorted element.

Forgetting to Increment the Left Pointer After Swapping Zeros

When swapping a 0 to the left boundary, both the left boundary pointer and the current pointer must advance. The left boundary moves to make room for the next 0, and the current pointer moves because the swapped element (which came from the left) is guaranteed to be 0 or 1, both of which are already correctly positioned.

from typing import List

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        zero = one = 0
        for two in range(len(nums)):
            tmp = nums[two]
            nums[two] = 2
            if tmp < 2:
                nums[one] = 1
                one += 1
            if tmp < 1:
                nums[zero] = 0
                zero += 1

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int zero = 0, one = 0;
        for (int two = 0; two < nums.size(); two++) {
            int tmp = nums[two];
            nums[two] = 2;
            if (tmp < 2) {
                nums[one++] = 1;
            }
            if (tmp < 1) {
                nums[zero++] = 0;
            }
        }
    }
};