Sort Colors

Medium Problem 14 of 151 Java and Python

Problem

An array nums holds n objects coloured red, white or blue, written as 0, 1 and 2. Sort it in place so the same colours are together, in the order red, white, blue.

Do not use the library sort function.

Example 1

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

Example 2

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

Constraints

1 ≤ n ≤ 300
nums[i] is 0, 1 or 2.
Follow-up: one pass with O(1) extra space.

Explanation

With only three values you could count them and rewrite the array, but that takes two passes.

In one pass, keep three regions: 0s before low, 2s after high, and 1s between low and mid. Look at nums[mid] and move it into its region.

Approach 1 · Better

Count, then overwrite

Time O(n), two passes
Space O(1)

Count the 0s, 1s and 2s, then write that many of each back into the array.

Count each colour.
Overwrite the array: count[0] zeros, then count[1] ones, then count[2] twos.

Java

class Solution {
    public void sortColors(int[] nums) {
        int[] count = new int[3];
        for (int num : nums) {
            count[num]++;
        }
        int i = 0;
        for (int color = 0; color < 3; color++) {
            for (int c = 0; c < count[color]; c++) {
                nums[i++] = color;
            }
        }
    }
}

Python

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        count = [0, 0, 0]
        for num in nums:
            count[num] += 1
        i = 0
        for color in range(3):
            for _ in range(count[color]):
                nums[i] = color
                i += 1

Approach 2 · Optimal

Dutch national flag

Time O(n), one pass
Space O(1)

Three pointers: low (next place for a 0), mid (current element) and high (next place for a 2).

Set low = mid = 0, high = n - 1.
While mid <= high: if nums[mid] == 0, swap with low, move low and mid.
If it is 1, just move mid.
If it is 2, swap with high and move high only: the swapped-in value has not been checked yet.

Java

class Solution {
    public void sortColors(int[] nums) {
        int low = 0;
        int mid = 0;
        int 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[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

Python

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        low, mid, high = 0, 0, len(nums) - 1
        while mid <= high:
            if nums[mid] == 0:
                nums[low], nums[mid] = nums[mid], nums[low]
                low += 1
                mid += 1
            elif nums[mid] == 1:
                mid += 1
            else:
                nums[mid], nums[high] = nums[high], nums[mid]
                high -= 1

Complexity compared

Approach	Time	Space
Better Count, then overwrite	O(n), two passes	O(1)
Optimal Dutch national flag	O(n), one pass	O(1)

Key takeaways

After swapping with high, do not move mid: the new value still needs a look.
The same three-way partition powers quicksort on arrays with many duplicates.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem