Generated by Codex with GPT-5

Quick facts

• Difficulty: MEDIUM
• Problem: Sort Colors
• Main tags: Array, Two Pointers, Sorting

What the problem is really asking

The input array contains only 0, 1, and 2. Those values represent three categories, and the goal is to reorder the array in place so all 0s come first, then all 1s, then all 2s.

The important part is not the final order itself. The interview signal is whether the candidate notices that this is not a general sorting problem. Because there are only three possible values, the solution can exploit that structure and beat ordinary comparison-based sorting.

The follow-up that usually matters most is whether this can be done in one pass with constant extra space.

A simple solution first

The easiest correct idea is counting.

Scan the array once, count how many 0s, 1s, and 2s there are, then overwrite the array with that many copies of each value in order.

That approach is already much better than calling a generic sort:

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

It is a strong baseline because it uses the fact that there are only three values. But it takes two passes over the array, so it does not satisfy the strongest follow-up.

The optimal idea: three-way partitioning

To get to the one-pass solution, it helps to stop thinking about sorting and start thinking about partitioning.

Maintain three regions:

• the left side already finalized as all 0s
• the right side already finalized as all 2s
• the middle still being examined

Use three pointers:

• next_zero_position: where the next 0 should be placed
• scan_index: the current index being inspected
• next_two_position: where the next 2 should be placed from the right

At every step:

• if the current value is 0, swap it to the left region, then move both next_zero_position and scan_index
• if the current value is 1, it is already in the correct middle region, so just move scan_index
• if the current value is 2, swap it into the right region and move next_two_position, but do not move scan_index yet

That last detail is the whole trick. After swapping with the right side, the new value that lands at scan_index has not been processed yet, so it must be examined before moving on.

This is the Dutch National Flag algorithm.

How to derive it in an interview

A clean way to derive the optimal solution is:

1. Start with counting, because it is the most direct way to use the fact that only three values exist.
2. Ask what extra work counting is doing. The answer is that it fully counts the array first and rewrites it later.
3. Realize the array does not need full sorting logic. It only needs each value moved into one of three buckets.
4. Turn those buckets into in-place regions and grow them as the scan moves forward.

Once that idea clicks, the pointer rules become natural instead of feeling memorized.

Why this solution works

The algorithm maintains a simple invariant throughout the scan:

• everything before next_zero_position is confirmed to be 0
• everything after next_two_position is confirmed to be 2
• everything between next_zero_position and scan_index - 1 is confirmed to be 1
• everything from scan_index through next_two_position is still unknown

Each branch shrinks the unknown region while preserving those guarantees. Because the unknown region gets smaller every step, the algorithm finishes after linear work.

The result is:

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

Python solution

In Python, the cleanest implementation is to separate the in-place partition logic into a helper function and keep the LeetCode Solution wrapper thin.

The core idea is to scan once while maintaining the three regions described above. This keeps the code short, but the important thing is that every pointer movement has a reason:

• placing a 0 grows the left finalized region
• seeing a 1 grows the middle finalized region
• placing a 2 grows the right finalized region

That mental model is more durable than trying to remember pointer updates by rote.

Interview follow-ups

What if the interviewer says one pass is not required?

The best answer is the counting approach. Count how many 0s, 1s, and 2s appear, then write those values back into the array in order. It is still O(n) time and O(1) extra space, and it is often the easiest solution to explain. The tradeoff is that it uses two passes instead of one. That makes it simpler, but slightly weaker than the Dutch National Flag solution if the interviewer explicitly asks for the strongest in-place approach.

Why does the algorithm not advance scan_index after swapping with the right side?

Because the value swapped in from the right has not been classified yet. If scan_index moved forward immediately, the algorithm could skip an unprocessed 0 or 2 and leave the array incorrectly partitioned. Rechecking the same index guarantees that every incoming value is processed exactly once. This is the subtle point that usually distinguishes a correct one-pass solution from an almost-correct one.

How would you prove the algorithm is correct?

The clean proof uses loop invariants. Before each iteration, the left segment contains only 0s, the middle-left segment contains only 1s, the right segment contains only 2s, and only the middle segment is unknown. Each branch of the algorithm preserves those statements while shrinking the unknown segment. When the scan ends, there is no unknown segment left, so the whole array must be correctly partitioned. This proof is usually more convincing in an interview than informal intuition because it explains exactly why each swap and pointer movement is safe.

How would you handle more than three distinct values?

If the number of distinct values is still small and known ahead of time, counting is usually the best answer because it stays simple and linear. If the values are arbitrary, then the problem becomes a real sorting problem again, and a general-purpose sort is usually the right tool. The Dutch National Flag trick works beautifully here because there are exactly three groups and the target ordering is fixed. That special structure is what makes the one-pass constant-space solution possible.

Production-ready code

from typing import List


def swap_values(values: List[int], left_index: int, right_index: int) -> None:
    """Swap two positions in place."""
    values[left_index], values[right_index] = values[right_index], values[left_index]


def sort_colors_in_place(colors: List[int]) -> None:
    """
    Reorder an array containing only 0, 1, and 2 in a single pass.

    Invariant during the scan:
    - colors[:next_zero_position] contains only 0s
    - colors[next_zero_position:scan_index] contains only 1s
    - colors[next_two_position + 1:] contains only 2s
    - colors[scan_index:next_two_position + 1] is the unknown region
    """
    next_zero_position = 0
    scan_index = 0
    next_two_position = len(colors) - 1

    while scan_index <= next_two_position:
        current_color = colors[scan_index]

        if current_color == 0:
            # Move the 0 into the left finalized region.
            swap_values(colors, scan_index, next_zero_position)
            next_zero_position += 1
            scan_index += 1
        elif current_color == 1:
            # 1 already belongs in the middle region.
            scan_index += 1
        elif current_color == 2:
            # Move the 2 into the right finalized region.
            # Do not advance scan_index yet because the incoming value
            # from the right has not been processed.
            swap_values(colors, scan_index, next_two_position)
            next_two_position -= 1
        else:
            raise ValueError(f"Unexpected color value: {current_color}")


class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """LeetCode entry point. Mutates nums in place."""
        sort_colors_in_place(nums)