Command Palette

Search for a command to run...

Hectal
Problem 14.2 · Sorting and Divide & ConquerMedium

Sort Colors

PatternTwo Pointers: Read and Write

What it teaches: Three-way partitioning (Dutch national flag) in one pass with three pointers.

Practise it on judges as “Sort Colors”.

The problem

nums contains only 0, 1 and 2. Sort it in place in one pass with O(1) space.

Example 1

Input: nums = [2, 0, 2, 1, 1, 0]
Output: [0, 0, 1, 1, 2, 2]

Constraints

  • 1 ≤ n ≤ 300
  • Values 0, 1, 2

Pattern clues in the wording

  • → Only three distinct values
  • → One pass, in place

These clues point to Two Pointers: Read and Write: A fast pointer reads every element and a slow pointer marks where the next kept element should be written.

Stuck? Take one hint at a time

Solution.java · starter
class Solution {
    public void sortColors(int[] nums) {
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
nums = [2,0,2,1,1,0]
[0,0,1,1,2,2]
2
nums = [2,0,1]
[0,1,2]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Optimal: Dutch national flag · O(n)
1

Optimal: Dutch national flag

Time O(n) Space O(1)

low = 0, mid = 0, high = n − 1. If nums[mid] is 0, swap with low and advance both; if 1, advance mid; if 2, swap with high and decrease high (don't advance mid: the swapped-in value is unchecked).

▶ Dry run: Three regionsnums = [2, 0, 2, 1, 1, 0]
2
0
↑lo↑mid
0
1
2
2
1
3
1
4
0
5
↑hi

Step 1/4nums[mid] = 2: swap with hi; hi−−.

Approach 1
class Solution {
    public 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] == 1) mid++;
            else swap(nums, mid, high--);
        }
    }

    private void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }
}

Verdict: One pass.

Before you submit

Edge cases and common mistakes

Test these inputs

  • All one colour
  • Already sorted
  • Reverse sorted

Mistakes people make

  • Advancing mid after swapping with high.

Interview

Follow-up questions

Where else is three-way partitioning used?