Two-Pointer Partition Walkthrough for Dutch Flag Beginners

Sorting arrays of 0s, 1s, and 2s in one pass seems magical until the pointers start crossing. This walkthrough shows how to maintain invariants, narrate the swap logic, and avoid the mistakes beginners make when practicing the Dutch National Flag pattern.

TL;DR

• Topic: In-place three-way partition using low, mid, and high pointers.
• Interview value: Shows invariant thinking and swap discipline without extra space.
• Core steps: grow mid pointer, swap 0s forward, swap 2s backward, leave 1s in place.
• Beginners often forget to decrement high after swapping or move both low and mid unnecessarily.
• You will learn a visual trace, a TypeScript snippet, common bugs, and practice prompts.

Beginner-Friendly Explanations

What Each Pointer Owns

• low-1: all confirmed 0s.
• mid-1: all confirmed 1s.
• high+1: all confirmed 2s.
  Everything between mid and high is unknown. The invariant is maintained by deciding the current mid value.

Why the Order of Actions Matters

Swapping a 2 to the back changes the element at mid, so you re-check mid without incrementing. Swapping a 0 forward places a known 0 before low, so both low and mid advance. This reasoning sounds strong in a mock interview routine.

Visual Layout

Draw three regions:

• [0 ... low-1] = zeros
• [low ... mid-1] = ones
• [mid ... high] = unknown
• [high+1 ... end] = twos
  Re-sketch after each swap to see movement instead of guessing.

Step-by-Step Learning Guidance

1) State the Invariant

Say out loud: "left side zeros, middle ones, right side twos, mid scans the unknown." Anchoring the invariant keeps swaps purposeful.

2) Initialize Pointers

Set low = 0, mid = 0, high = n - 1. Handle empty arrays and single-element cases first, echoing habits from the interview communication guide.

3) Process mid Until It Crosses high

While mid <= high, inspect nums[mid]:

• If 0: swap with nums[low], increment low and mid.
• If 1: just increment mid.
• If 2: swap with nums[high], decrement high; re-check mid.

4) Narrate the Why

During practice, explain "I keep mid in place after a 2-swap because the incoming value is unclassified." This builds interview fluency reinforced by the AI prep primer.

5) Validate With Small Arrays

Trace [2,0,1,2,0] on paper. After each operation, list the three regions. This habit prevents hand-wavy mistakes later.

Visualizable Example: Dutch National Flag in TypeScript

function dutchFlagSort(nums: number[]): void {
  let low = 0;
  let mid = 0;
  let high = nums.length - 1;

  while (mid <= high) {
    if (nums[mid] === 0) {
      [nums[low], nums[mid]] = [nums[mid], nums[low]];
      low++;
      mid++;
    } else if (nums[mid] === 1) {
      mid++;
    } else {
      [nums[mid], nums[high]] = [nums[high], nums[mid]];
      high--;
    }
  }
}

Notice that mid is not incremented in the 2-swap branch; the element swapped in might be 0, requiring another swap forward.

Practical Preparation Strategies

Practice With Timed Drills

Solve three arrays of sizes 5, 10, and 15 in under two minutes each. Time pressure reveals whether your invariant explanation is crisp.

Add Edge Cases

Include arrays like [2,2,2], [0,0,1], and [1,0,2,1]. Compare traces across runs. For more two-pointer guidance, see two pointers intuition for LeetCode beginners.

Use Light Guidance

Tools like LeetCopilot can flag when you accidentally increment mid after a 2-swap, nudging you back to the invariant without spoiling the solution.

Common Mistakes to Avoid

Moving Both low and mid After a 2-Swap

Re-check mid instead; the swapped-in value is unknown.

Forgetting to Decrement high

If high does not move, the loop may never terminate when trailing 2s exist.

Losing the Invariant Description

If you cannot articulate which region is sorted, pause and restate it before continuing.

Ignoring Already-Sorted Inputs

Still run the loop; skipping checks can hide off-by-one errors.

FAQ

How do I know the pointers are positioned correctly?

After each iteration, verify the three regions match the invariant; mid should always point to the first unknown.

What should I practice before this pattern?

Be comfortable with array swaps and while-loop conditions; then move to this partitioning approach.

Is this pattern important for interviews?

Yes—it's a concise test of pointer discipline, invariants, and communication.

Can this extend beyond 0/1/2 arrays?

Yes, the idea generalizes to k-way partitions, though implementation complexity grows.

Conclusion

Mastering the two-pointer partition for the Dutch flag builds confidence in invariants, disciplined swaps, and clear narration. Keep tracing small arrays, speak the invariant out loud, and you will carry this structure into broader in-place partitioning problems with less guesswork.