Start practising

Sort Colors

Medium Arrays & Hashing Dutch National Flag Original on LeetCode

Sort Colors is a medium arrays & hashing problem solved with the dutch national flag pattern. The best approach, optimal (dutch national flag, one pass), runs in O(n) time and O(1) space. Below are 2 approaches in Java, from counting (two passes) up.

Problem

The array holds only 0, 1 and 2 (think red, white and blue). Sort it in place so equal values are together in the order 0, 1, 2, without using a library sort.

Follow-up: can you do it in a single pass with constant space?

Examples

Example 1

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

Example 2

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

Constraints

  • 1 <= nums.length <= 300
  • Each value is 0, 1 or 2.
  • Sort in place in one pass, without a library sort.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
Counting (two passes)O(n)O(1)
Optimal (Dutch National Flag, one pass)O(n)O(1)

1Counting (two passes)

TimeO(n)
SpaceO(1)

Count the 0s, 1s and 2s, then overwrite the array in order.

  1. Count each value.
  2. Write that many 0s, then 1s, then 2s.
Java
class Solution {
    public void sortColors(int[] nums) {
        int[] c = new int[3];
        for (int x : nums) c[x]++;
        int k = 0;
        for (int v = 0; v < 3; v++)
            while (c[v]-- > 0) nums[k++] = v;
    }
}

2Optimal (Dutch National Flag, one pass)

TimeO(n)Each step either advances mid or shrinks high.
SpaceO(1)

Keep low (end of the 0s), mid (scanner) and high (start of the 2s). A 0 at mid swaps to low and both move. A 1 just moves mid. A 2 swaps to high and only high moves, because the value swapped in has not been checked yet.

  1. low = mid = 0, high = n - 1.
  2. nums[mid] == 0: swap(low, mid), low++, mid++.
  3. nums[mid] == 1: mid++.
  4. nums[mid] == 2: swap(mid, high), high--.
Java
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;
    }
}

Edge cases to test

  • Only one colour present
  • Already sorted or reverse sorted

Hints

Hint 1

Keep three regions: 0s at the front, 2s at the back, 1s in the middle. Which pointer should not move after a swap with the back?

FAQ

What is the best time complexity for Sort Colors?

Optimal (Dutch National Flag, one pass) runs in O(n) time and O(1) extra space. Each step either advances mid or shrinks high.

Which pattern does Sort Colors use?

It is a arrays & hashing problem that uses the dutch national flag pattern.

Is there a brute force solution for Sort Colors?

Yes. Counting (two passes) takes O(n) time and O(1) space. Count the 0s, 1s and 2s, then overwrite the array in order.

Which edge cases should I test for Sort Colors?

Only one colour present; Already sorted or reverse sorted.