Sort Colors (Dutch Flag)

medium

Sort array of 0s, 1s, 2s in-place using three pointers

Sort Colors (Dutch Flag)

Key Insight

Three pointers: low for 0s, mid scans, high for 2s. One pass O(n).

Step 1Setup
low
mid
2
0
0
1
2
2
1
3
1
4
high
0
5

low=0 (0s go here), mid=0 (scanner), high=5 (2s go here)

1 / 5

Learn the Pattern

Two PointersUse two pointers to traverse an array or string, reducing time complexity from O(n^2) to O(n) for problems involving pairs or subarrays.
SortingUse sorting as a preprocessing step to simplify problems, or apply partition logic for in-place rearrangement. Many interview problems become trivial once the array is sorted.
Practice the Code

Step-by-Step Walkthrough: Sort Colors (Dutch Flag)

Three pointers: low for 0s, mid scans, high for 2s. One pass O(n).

  1. Setup

    low=0 (0s go here), mid=0 (scanner), high=5 (2s go here)

  2. Found 2

    mid=0 sees 2. Swap with high. Decrease high.

  3. Found 0

    mid=0 sees 0. Swap with low. Increase both.

  4. Found 1

    mid sees 1. It's in the right zone. Just move mid.

  5. Done

    mid > high, sorting complete!