Sort Colors

The trap in the Sort Colors solution is assuming that “only three values” makes the problem trivial. Counting works. The interview version asks you to see the stronger structure: partition the array in one pass, in place, while never losing track of an unclassified value.

The useful model is three regions:

• known 0s on the left,
• unknown values in the middle,
• known 2s on the right.

A third pointer tracks the 1s between them. The critical rule is simple:

When a 2 is swapped with the right side, inspect the incoming value again. It came from the unknown region.

That rule is the difference between a correct Dutch National Flag Python implementation and one that silently skips elements.

Read the Contract Before Choosing the Pattern

The array contains only 0, 1, and 2. The required order is:

0s, then 1s, then 2s

The array must be modified in place, and the library sorting function cannot be used. The target is therefore:

• Time: O(n)
• Extra space: O(1)
• Mutation: rearrange the existing array rather than building a second one

The fixed value domain is the main recognition clue. We are not sorting arbitrary values that need pairwise comparison. We are grouping three known categories in a known order.

That changes the design. Instead of asking, “Which two elements should I compare?”, ask:

Which parts of the array have already been classified, and where is the remaining uncertainty?

This is still a Two Pointers problem, but the pointers do different jobs from the familiar sorted-array patterns. They do not search for a pair. They mark boundaries around an unknown interval.

Use a Baseline to Expose the Real Constraint

A library call would solve the ordering immediately:

nums.sort()

But it violates the problem contract. It also hides the useful structure: the input has only three possible values.

A valid baseline is counting:

1. Count how many 0s, 1s, and 2s exist.
2. Overwrite the array with that many values in order.

For example, if the counts are:

0: 2
1: 2
2: 2

rewrite the array as:

[0, 0, 1, 1, 2, 2]

This already gives O(n) time and O(1) extra space because there are only three counters. It is a reasonable solution if the interviewer accepts two passes: one to count and one to overwrite.

But it leaves a more interesting optimization available. We can classify values and place them during the same scan if we maintain three regions. The array itself becomes the working storage. No count array. No second pass. No extra container.

The goal is not merely fewer lines of code. The goal is to make the unknown portion shrink until nothing remains.

Model the Array as Three Regions

Use three indices:

• low: the first position that is not known to be a 0
• mid: the next position to inspect
• high: the last position that is not known to be a 2

At every point in the algorithm, maintain this invariant:

• nums[0:low] contains only 0s.
• nums[low:mid] contains only 1s.
• nums[mid:high + 1] is unknown.
• nums[high + 1:] contains only 2s.

The Python slice notation is useful here even though the algorithm does not create slices. It describes ranges; it does not allocate them.

Initially:

low = 0
mid = 0
high = len(nums) - 1

Both known regions are empty:

• nums[0:0] contains no 0s.
• nums[0:0] contains no 1s.
• nums[high + 1:] is empty because high is the final index.

The unknown region is the entire array.

The loop runs while:

mid <= high

Once mid passes high, the unknown interval is empty. Every position belongs to a classified region.

Derive Each Pointer Update

Inspect nums[mid]. There are only three cases.

Value at mid	Action	Pointer movement
0	Swap it into the low region	Increment low and mid
1	Leave it in the middle region	Increment mid
2	Swap it into the high region	Decrement high; keep mid fixed

The last row deserves most of your attention.

When the value is 0

A 0 belongs before all known 1s. Swap it with nums[low]:

nums[low], nums[mid] = nums[mid], nums[low]

Then:

low += 1
mid += 1

Why can both pointers move?

Before the swap, positions before low are known 0s, and positions from low through mid - 1 are known 1s.

• The inspected 0 moves to low, expanding the known-0 region.
• The value moved from low to mid was already in the known-1 region. If low == mid, it is the same 0 and no new value needs inspection.

So the new value at mid is already classified.

When the value is 1

A 1 belongs between the known 0s and known 2s. It is already in the correct category:

mid += 1

This extends the known-1 region by one position.

When the value is 2

A 2 belongs at the right:

nums[mid], nums[high] = nums[high], nums[mid]
high -= 1

Do not increment mid.

The incoming value came from nums[high], which was inside the unknown region. It could be a 0, a 1, or another 2. Until you inspect it, you do not know which region it belongs to.

This is the most common implementation failure:

elif nums[mid] == 2:
    swap(nums, mid, high)
    high -= 1
    mid += 1  # bug

That unconditional increment can skip a newly swapped-in 0 or 1. The array may look nearly sorted while still containing an unclassified value in the middle.

The pointer should advance only when the value currently at mid has been classified.

Prove Correctness and Termination

A useful proof has three parts: initialization, maintenance, and termination.

Initialization

Set:

low = 0
mid = 0
high = len(nums) - 1

The known-0 and known-1 regions are empty. The known-2 region is also empty. Therefore the invariant holds before the first iteration.

Maintenance

Assume the invariant holds at the beginning of an iteration.

Case nums[mid] == 0

Swap nums[mid] with nums[low].

• The 0 moves to the end of the known-0 prefix.
• The value moved to mid came from the known-1 region, unless low == mid, in which case no distinct value moved.
• Incrementing both low and mid preserves the invariant.

The known 0 region grows, and the unknown region shrinks.

Case nums[mid] == 1

The value at the unknown region's front already belongs in the middle.

• Incrementing mid adds it to the known-1 region.
• The known 0 and known 2 regions do not change.

The invariant remains true.

Case nums[mid] == 2

Swap nums[mid] with nums[high].

• The 2 moves to the beginning of the known-2 suffix.
• Decrementing high expands that suffix.
• The value moved into mid is still unknown, so mid does not move.

The invariant remains true because the incoming value stays at the front of the unknown interval until the next iteration.

Termination

Each iteration makes progress:

• A 0 increments mid.
• A 1 increments mid.
• A 2 decrements high.

Therefore the interval from mid through high shrinks. Eventually:

mid > high

At that point there are no unknown positions left. The invariant's three classified regions cover the entire array:

0s | 1s | 2s

The algorithm performs constant work per iteration and shrinks the unknown interval every time, so it runs in O(n) time. It stores only three indices and uses swaps with constant temporary storage, so its extra space is O(1).

Dry-Run the Reinspection Case

Consider:

nums = [2, 0, 2, 1, 1, 0]

The state changes as follows:

low	mid	high	Inspected value	Action	Array after action
0	0	5	2	Swap with high, decrement high	[0, 0, 2, 1, 1, 2]
0	0	4	0	Swap with low, increment low, mid	[0, 0, 2, 1, 1, 2]
1	1	4	0	Swap with low, increment low, mid	[0, 0, 2, 1, 1, 2]
2	2	4	2	Swap with high, decrement high	[0, 0, 1, 1, 2, 2]
2	2	3	1	Leave in place, increment mid	[0, 0, 1, 1, 2, 2]
2	3	3	1	Leave in place, increment mid	[0, 0, 1, 1, 2, 2]

The first step shows the reinspection rule clearly:

[2, 0, 2, 1, 1, 0]
 ^

The 2 at index 0 swaps with the rightmost unknown value, a 0:

[0, 0, 2, 1, 1, 2]
 ^

That new 0 is now at mid. If you incremented mid immediately after handling the original 2, you would skip it. In this particular input, a later arrangement might still appear correct by coincidence. That is not a proof. The state transition is invalid because the swapped-in value was never classified.

Implement the Python Solution

The implementation should mirror the invariant directly. The names describe obligations, not arbitrary positions:

def sort_colors(nums: list[int]) -> None:
    low = 0
    mid = 0
    high = len(nums) - 1

    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:  # nums[mid] == 2
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1
            # Keep mid fixed: the incoming value is still unknown.

This function mutates nums and returns None. It does not call sort() or sorted(), and it does not allocate a second array.

If an interviewer asks for the Dutch National Flag Python approach, do not start by reciting the label. Start by naming the regions:

known 0s | known 1s | unknown | known 2s

Then derive the update from the source of each swapped value. The code becomes a translation of the state model rather than a snippet you hope to remember under pressure.

Complexity, Edge Cases, and Interview Checks

The complexity is:

• Time: O(n)
• Extra space: O(1)

The time bound comes from the shrinking unknown interval. A 0 or 1 advances mid; a 2 moves high left. The space bound comes from storing only three indices and using constant-size swap storage.

Check these cases before you trust the implementation:

• A single element: [0], [1], or [2]
• All 0s
• All 1s
• All 2s
• Already sorted input: [0, 0, 1, 1, 2, 2]
• Reverse order: [2, 2, 1, 1, 0, 0]
• Repeated values mixed throughout
• A 0 when low == mid
• A swap where mid == high
• A 2 swapping with another 2

The last two cases matter because swaps can occur at the same index or move a value that looks identical to the one being classified. The pointer updates must follow the invariant, not the visual appearance of the array.

My interview checklist is short:

1. Name the three classified regions and the unknown interval.
2. State the invariant using index ranges.
3. Explain why 0 advances both low and mid.
4. Explain why 1 advances only mid.
5. Explain why 2 decrements only high.
6. Dry-run a 2 that swaps in an unclassified value.
7. Stop when mid > high.

The transferable rule is broader than this one array:

When values belong to a small, ordered set of categories and the array must be rearranged in place, maintain known regions around an unknown interval. Advance a pointer only when the value at its new position is already classified.

For the Sort Colors solution, that rule produces the three-way partition. In another problem, the categories or boundaries may change. The reasoning move stays the same: define what is known, isolate what is unknown, and make every pointer update earn its place.