← Back to DSA Animator
Sort Colors LC #75 Medium Dutch National Flag
Problem

Given an array nums with n objects colored red (0), white (1), or blue (2), sort them in-place so that objects of the same color are adjacent, in the order red, white, and blue. You must solve this without using the library's sort function.

Example 1
Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Constraints: n == nums.length  |  1 ≤ n ≤ 300  |  nums[i] ∈ {0, 1, 2}
Try Examples
Custom:
Approach
3-Way Partition (Dutch National Flag)
Three pointers lo, mid, hi partition the array into regions: [0..lo-1]=all 0s, [lo..mid-1]=all 1s, [hi+1..n-1]=all 2s. Sweep mid through the array: swap 0s left, 2s right, skip 1s. O(n) time, O(1) space!
Array
0 = Red 1 = White 2 = Blue
nums[] — current state
Variables
lo
—
mid
—
hi
—
nums[mid]
—
Step Logic
Press ▶ Play or Next Step to begin.
🎉
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
lo=0, mid=0, hi=n-1
2
nums[mid]==0 → swap(lo,mid), lo++, mid++
3
nums[mid]==1 → mid++ only
4
nums[mid]==2 → swap(mid,hi), hi-- (no mid++)
Time
O(n)
Space
O(1)
Why It Works

Invariant: [0..lo-1] all 0s, [lo..mid-1] all 1s, [hi+1..n-1] all 2s. When mid sees 0, swap with lo (known 1) — both advance. When 2, swap with hi (unknown) — only hi shrinks since new value at mid is unclassified. When 1, just advance mid.