Step 3: Solve Problems on Arrays [Easy -> Medium -> Hard]›Medium
Sort 0s, 1s, and 2s & The Three-Bucket Sorter
MediumFunction: sortAnArrayOf0S1SAnd2S()
ASCI Mission Breakdown • Simple as Hell
"Sort an array of 0s, 1s, and 2s in-place in a single pass."
Real-World Metaphor:
Imagine organizing three colored poker chips: red (0), white (1), and blue (2). You hold two dividing markers: anything before low is red, anything after high is blue, and white sits in the middle.
Interactive Visual WalkthroughARRAY-POINTERS
Step 1 / 3
Bottles: [2, 0, 2, 1, 1, 0]
mid
2
[0]
0
[1]
2
[2]
1
[3]
1
[4]
high
0
[5]
Memory Notepad / State Tracker
Action:Swap mid & high
Evaluating
1. Inspect Index 0 (Value 2)
mid points to 2. Swap with high! 2 moves to the back.
How to Think About This (Mental Model)
Maintain three pointers: low = 0, mid = 0, high = n - 1.
While mid <= high:
If nums[mid] === 0: swap(low, mid), low++, mid++.
If nums[mid] === 1: mid++.
If nums[mid] === 2: swap(mid, high), high-- (do not increment mid!).
### The Mission
You are sorting recycled bottles coming down a conveyor belt. The bottles come in three types:
- **0**: Aluminum Cans
- **1**: Glass Bottles
- **2**: Plastic Jugs
Your mission is to sort them **in-place** so that all 0s come first, followed by all 1s, and finally all 2s. Can you do this in a single pass without using standard sort? (Dutch National Flag algorithm).
Examples
Example 1
Input: nums = [5,2,3,1]
Output: [1,2,3,5]
Example 2
Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]
Constraints
1 <= nums.length <= 5 * 10^4
-5 * 10^4 <= nums[i] <= 5 * 10^4
Topic Tags:
Solve Problems on Arrays [Easy -> Medium -> Hard]MediumsortAnArrayOf0S1SAnd2S