Dutch National Flag Problem

So this time I was given the below 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

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

My brain immediately went:

I had a gut feeling this was about rearranging and grouping elements. My intuition screamed "pointers!" Not just two, but three. Also I get to know that this classic problem is often called the Dutch National Flag problem.

The Game Plan: Three Pointers for Three Colors
The goal is to partition the array into three sections: all the 0s at the beginning, all the 1s in the middle, and all the 2s at the end.

To do this in a single pass, we'll use three pointers:

• left: This pointer marks the boundary for our "red" (0) section. Everything to the left of left is a confirmed 0.

• middle: This is our main iterator. It scans the array, and its job is to figure out where the element nums[middle] belongs.

• right: This pointer marks the boundary for our "blue" (2) section. Everything to the right of right is a confirmed 2.

Our loop will run as long as middle <= right, shrinking the "unknown" section between middle and right until it disappears.

The Logic in Action
We iterate through the array with our middle pointer and handle three simple cases:

Case 1: nums[middle] is a 0 (Red) 🔴
If nums[middle] is a 0, it belongs in the left section. So, we swap the element at middle with the element at left.

swap(nums[left], nums[middle]);

Since we now have a confirmed 0 at the left position, we can advance our left pointer. We also advance the middle pointer because the element we just swapped into the middle position has already been processed (we'll dive into why in a moment).

left++;
middle++;

Case 2: nums[middle] is a 1 (White) ⚪
If nums[middle] is a 1, it's already in the right potential spot! The middle section is where 1s are supposed to live. We don't need to swap anything. We just move on to the next element.

middle++;

Case 3: nums[middle] is a 2 (Blue) 🔵
If nums[middle] is a 2, it belongs at the end of the array, in the right section. So, we swap it with the element at the right pointer.

swap(nums[middle], nums[right]);

After the swap, we know the element now at right is a 2, so we can shrink our right boundary inward.

right--;

But notice we don't advance middle here! Why? The element we just received from the right position is a complete unknown. It could be a 0, 1, or even another 2. We need to re-evaluate the new element at nums[middle] in the next loop iteration.

The "Aha!" Moment: Why Pointer Moves Differ

This was the key insight for me:

When we swap nums[middle] == 0 with nums[left], we know the element coming to middle was already in the processed zone (left of middle). Because of our algorithm's structure, any element between left and middle can only be a 1. So, after the swap, nums[middle] is guaranteed to be a 1 (or a 0 if left and middle started at the same spot). In either case, the element at middle is handled, and we can confidently move middle forward.

When we swap nums[middle] == 2 with nums[right], the element coming to middle is from the unprocessed, unknown part of the array. We must re-check it to see if it's a 0, 1, or 2 before moving middle.

This simple but powerful logic allows us to sort the array in one pass with constant extra space.