DSA-012 · Dutch-national-flag partition
Sort Colors
Intermediate · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 29527 deterministic checks. Learner drafts are not executed.
Understand the problem
Sort an array containing only 0, 1, and 2 in place without a comparison sort.
- nums is non-null with 0–100,000 entries, each exactly 0, 1, or 2. Other integers are outside the contract; this method does not validate or partially repair invalid input.
- Return void, preserving the array object and the count of each color. The final values must be nondecreasing. Empty input is allowed.
- The optimized algorithm uses O(1) extra space and one pass over the unknown region. Stability for separately labeled records is not promised.
Examples
Input:
[2,0,2,1,1,0]
Output:[0,0,1,1,2,2]Every occurrence is partitioned by its bounded key.
Input:
[2,0,1]
Output:[0,1,2]A swap from the high end can bring an unknown value into mid.
Before you start
- Array indexing and inclusive pointer bounds
- Loop invariants and Java value versus reference semantics
Recognize the structure
Three known keys allow three owned regions and one unknown interval. Classification shrinks the unknown interval on every iteration; it is not a general comparison-sorting problem.
Try before revealing
Hint 1
Separate the processed values from an unknown interval.
Hint 2
Which swap brings a known value back, and which brings an unknown one?
Hint 3
Use low/mid/high and recheck mid after swapping with high.
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Count then rewrite
Count occurrences in three counters, then write that many zeros, ones, and twos. For [2,0,1,2], counts are [1,1,2]; rewriting gives [0,1,2,2]. It takes O(n) time and O(1) space but makes two passes. The pointer version combines discovery and placement.
Improve the baseline
Name four regions
[0,low) holds zeros; [low,mid) holds ones; [mid,high] is unknown; (high,n) holds twos.
Place zero or one
A zero swaps with low and advances low and mid; the displaced value is a known one unless low==mid. A one extends the known-one region by advancing mid.
Place two and recheck
Swap a two at mid with high and decrease high. The incoming value was unknown, so keep mid fixed and classify it next.
Why it is correct
Initialization
low=mid=0 and high=n-1 make the three known regions empty and the entire input unknown. The invariant holds even when n=0.
Preservation
The zero branch adds one zero and preserves the ones; the one branch adds one one; the two branch adds one two without claiming knowledge of its replacement. Swaps preserve multiplicities.
Completion
Each branch decreases high-mid+1 by one. When mid>high, the unknown region is empty and the three adjacent regions form the sorted array.
Complete Java reference and baseline
Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.
public final class Solution {
public static void sortColors(int[] nums) {
int low = 0, mid = 0, high = nums.length - 1;
while (mid <= high) {
if (nums[mid] == 0) {
swap(nums, low++, mid++);
} else if (nums[mid] == 2) {
swap(nums, mid, high--);
} else {
mid++;
}
}
}
private static void swap(int[] nums, int i, int j) {
int temporary = nums[i]; nums[i] = nums[j]; nums[j] = temporary;
}
public static void baseline(int[] nums) {
int[] counts = new int[3];
for (int value : nums) counts[value]++;
int write = 0;
for (int color = 0; color < 3; color++) for (int k = 0; k < counts[color]; k++) nums[write++] = color;
}
}
Read the meaningful blocks
mid<=high
The final unknown cell must be processed; mid<high would skip it.
Postincrements
The zero branch consumes a known placement at both low and mid. The two branch consumes only high.
Bounded-key promise
The else branch means one only because the input alphabet is exactly {0,1,2}; broadening it requires validation or a different algorithm.
Complexity
O(n) time because every iteration shrinks the unknown region, including repeated visits to mid. O(1) auxiliary space; output is in place.
The counting baseline is also O(n) time and O(1) space. The optimization is a single classification pass, not a better asymptotic bound. Swaps need not preserve the relative order of labeled equal-key records.
Exact-state walkthroughs
Reveal normal and boundary traces
Unknown values swapped in from high
Input: [2,0,2,1,1,0] · Final state: [0,0,1,1,2,2]
Step 1 of 8: Initialize three empty known regions.
[0,low) is zero, [low,mid) is one, (high,n) is two, and [mid,high] is unknown.
- 0: 2
- 1: 0
- 2: 2
- 3: 1
- 4: 1
- 5: 0
| Variable | Value |
|---|---|
| values | [2,0,2,1,1,0] |
| low | 0 |
| mid | 0 |
| high | 5 |
See the affected Java block
1 public final class Solution { 2 public static void sortColors(int[] nums) { 3 int low = 0, mid = 0, high = nums.length - 1; 4 while (mid <= high) { 5 if (nums[mid] == 0) { 6 swap(nums, low++, mid++); 7 } else if (nums[mid] == 2) { 8 swap(nums, mid, high--); 9 } else { 10 mid++; 11 } 12 } 13 } 14 private static void swap(int[] nums, int i, int j) { 15 int temporary = nums[i]; nums[i] = nums[j]; nums[j] = temporary; 16 } 17 public static void baseline(int[] nums) { 18 int[] counts = new int[3]; 19 for (int value : nums) counts[value]++; 20 int write = 0; 21 for (int color = 0; color < 3; color++) for (int k = 0; k < counts[color]; k++) nums[write++] = color; 22 } 23 } 24
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Initialize three empty known regions.
[0,low) is zero, [low,mid) is one, (high,n) is two, and [mid,high] is unknown.
- values
[2,0,2,1,1,0]- low
0- mid
0- high
5
- Classify one unknown occurrence.
Known regions satisfy their colors; the unknown interval shrank by exactly one. A high swap leaves its incoming value unknown.
- values
[0,0,2,1,1,2]- low
0- mid
0- high
4- oldMid
0- oldLow
0- oldHigh
5- value
2
- Classify one unknown occurrence.
Known regions satisfy their colors; the unknown interval shrank by exactly one. A high swap leaves its incoming value unknown.
- values
[0,0,2,1,1,2]- low
1- mid
1- high
4- oldMid
0- oldLow
0- oldHigh
4- value
0
- Classify one unknown occurrence.
Known regions satisfy their colors; the unknown interval shrank by exactly one. A high swap leaves its incoming value unknown.
- values
[0,0,2,1,1,2]- low
2- mid
2- high
4- oldMid
1- oldLow
1- oldHigh
4- value
0
- Classify one unknown occurrence.
Known regions satisfy their colors; the unknown interval shrank by exactly one. A high swap leaves its incoming value unknown.
- values
[0,0,1,1,2,2]- low
2- mid
2- high
3- oldMid
2- oldLow
2- oldHigh
4- value
2
- Classify one unknown occurrence.
Known regions satisfy their colors; the unknown interval shrank by exactly one. A high swap leaves its incoming value unknown.
- values
[0,0,1,1,2,2]- low
2- mid
3- high
3- oldMid
2- oldLow
2- oldHigh
3- value
1
- Classify one unknown occurrence.
Known regions satisfy their colors; the unknown interval shrank by exactly one. A high swap leaves its incoming value unknown.
- values
[0,0,1,1,2,2]- low
2- mid
4- high
3- oldMid
3- oldLow
2- oldHigh
3- value
1
- Final in-place state; Java returns void.
All required values have been finalized under the declared contract.
- result
[0,0,1,1,2,2]
One final unknown zero
Input: [1,0] · Final state: [0,1]
Step 1 of 4: Initialize three empty known regions.
[0,low) is zero, [low,mid) is one, (high,n) is two, and [mid,high] is unknown.
- 0: 1
- 1: 0
| Variable | Value |
|---|---|
| values | [1,0] |
| low | 0 |
| mid | 0 |
| high | 1 |
See the affected Java block
1 public final class Solution { 2 public static void sortColors(int[] nums) { 3 int low = 0, mid = 0, high = nums.length - 1; 4 while (mid <= high) { 5 if (nums[mid] == 0) { 6 swap(nums, low++, mid++); 7 } else if (nums[mid] == 2) { 8 swap(nums, mid, high--); 9 } else { 10 mid++; 11 } 12 } 13 } 14 private static void swap(int[] nums, int i, int j) { 15 int temporary = nums[i]; nums[i] = nums[j]; nums[j] = temporary; 16 } 17 public static void baseline(int[] nums) { 18 int[] counts = new int[3]; 19 for (int value : nums) counts[value]++; 20 int write = 0; 21 for (int color = 0; color < 3; color++) for (int k = 0; k < counts[color]; k++) nums[write++] = color; 22 } 23 } 24
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Initialize three empty known regions.
[0,low) is zero, [low,mid) is one, (high,n) is two, and [mid,high] is unknown.
- values
[1,0]- low
0- mid
0- high
1
- Classify one unknown occurrence.
Known regions satisfy their colors; the unknown interval shrank by exactly one. A high swap leaves its incoming value unknown.
- values
[1,0]- low
0- mid
1- high
1- oldMid
0- oldLow
0- oldHigh
1- value
1
- Classify one unknown occurrence.
Known regions satisfy their colors; the unknown interval shrank by exactly one. A high swap leaves its incoming value unknown.
- values
[0,1]- low
1- mid
2- high
1- oldMid
1- oldLow
0- oldHigh
1- value
0
- Final in-place state; Java returns void.
All required values have been finalized under the declared contract.
- result
[0,1]
Test the contract
Input:
[]
Output:[]The unknown interval is initially empty.
Input:
[2,2,2]
Output:[2,2,2]mid stays fixed while high retreats.
Input:
[1,0]
Output:[0,1]Inclusive final unknown cell.
Input:
[0,0,1,2]
Output:[0,0,1,2]Already partitioned input.
Common mistakes and counterexamples
Advance mid after a high swap
Counterexample: [1,2,0] can finish as [1,0,2] if the incoming zero is skipped.
Keep mid fixed after placing a two.
Stop at mid<high
Counterexample: [1,0] needs its remaining unknown zero classified.
Continue through mid==high.
Assume the swap-based partition is stable
Counterexample: A high swap can reverse labeled records with the same color.
Do not promise stability; use a stable strategy if payload order matters.
Follow-ups
Generalize to k small colors.
Count k categories in O(n+k) time and O(k) storage. A three-region proof does not extend automatically to an unbounded number of keys.
Require stable records.
A stable extra-buffer partition can preserve encounter order within each category. Overwriting color counts would destroy associated payloads.
Validate arbitrary integers.
Validate the full input before any mutation if invalid input must leave the array unchanged. Document the error behavior and the extra pass.
Your Java attempt
Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.
Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.
No unsaved text changes · 85/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.