Sort Colors

Sort Colors

What is this problem about?

The "Sort Colors" problem, also famously known as the "Dutch National Flag Problem," is a classic algorithmic challenge. You are given an array containing $0$s, $1$s, and $2$s (representing the colors red, white, and blue), and you must sort them in-place so that all $0$s are first, followed by $1$s, and then $2$s.

The catch? You cannot use the library's sort function. The goal is to solve it in a single pass ($O(N)$) using constant extra space ($O(1)$). This makes it a high-stakes test of your pointer manipulation skills.

Why is this asked in interviews?

This question is asked by virtually every major tech company, including Google, Meta, and Amazon. It is the ultimate test of "In-Place" array manipulation. It requires you to maintain three pointers and carefully manage the state as you swap elements. It evaluates your ability to handle complex loop invariants and your attention to detail regarding when to advance pointers.

Algorithmic pattern used

The pattern is the 3-Way Partitioning (or Dutch National Flag algorithm).

• low: Points to where the next 0 should go.
• mid: Current element being inspected.
• high: Points to where the next 2 should go. Logic:
• If nums[mid] == 0: swap with low, increment both low and mid.
• If nums[mid] == 1: just increment mid.
• If nums[mid] == 2: swap with high, decrement high (do NOT increment mid yet, as the new nums[mid] needs to be checked).

Example explanation

Input: [2, 0, 2, 1, 1, 0]

1. mid = 0 (val 2). Swap with high. [0, 0, 2, 1, 1, 2]. high = 4.
2. mid = 0 (val 0). Swap with low. [0, 0, 2, 1, 1, 2]. low = 1, mid = 1.
3. mid = 1 (val 0). Swap with low. [0, 0, 2, 1, 1, 2]. low = 2, mid = 2.
4. mid = 2 (val 2). Swap with high. [0, 0, 1, 1, 2, 2]. high = 3.
5. mid = 2 (val 1). Increment mid.
6. mid = 3, high = 3. Loop ends. Result: [0, 0, 1, 1, 2, 2].

Common mistakes candidates make

The most frequent mistake is incrementing the mid pointer after swapping with high. Since you don't know what was at high, you must re-evaluate the element swapped into the mid position. Another mistake is using a Two-Pass approach (counting 0s, 1s, and 2s first), which is $O(N)$ but doesn't meet the "One-Pass" challenge often issued by interviewers. Handling the edge cases where the array has only one color is also a common pitfall.

Interview preparation tip

The "Sort Colors interview question" is all about loop invariants. Practice explaining why the pointers move the way they do. Being able to visualize the array as three sections (0s, 1s, and 2s) and one un-inspected middle section will help you write the code correctly under pressure. This is one of those problems where the logic is elegant but easy to trip over if you don't understand the "why" behind each move.