27. Sort Colors · DSA Practice

nums contains only 0, 1 and 2 (red, white, blue). Sort it in place in one pass without using a library sort.

Example 1

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

Output: [0,0,1,2,2]

Example 2

Input: nums = [1]

Output: [1]

Hint 1

Keep three regions: 0s on the left, 2s on the right, 1s in the middle.

SortingTwo Pointers

Approach 1: Counting sort

Count 0s, 1s and 2s, then overwrite.

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

Approach 2: Dutch national flag ✅

Three pointers partition the array in a single pass.

⏱ Time O(n)💾 Space O(1)

Reference solution for Dutch national flag (time O(n), space O(1)). Each solution passes every test in all four languages.

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        lo, mid, hi = 0, 0, len(nums) - 1      # Dutch national flag
        while mid <= hi:
            if nums[mid] == 0:
                nums[lo], nums[mid] = nums[mid], nums[lo]
                lo += 1
                mid += 1
            elif nums[mid] == 1:
                mid += 1
            else:
                nums[mid], nums[hi] = nums[hi], nums[mid]
                hi -= 1                        # do not advance mid: the swapped-in value is unchecked

class Solution {
    public void sortColors(int[] nums) {
        int lo = 0, mid = 0, hi = nums.length - 1;   // Dutch national flag
        while (mid <= hi) {
            if (nums[mid] == 0) { int t = nums[lo]; nums[lo++] = nums[mid]; nums[mid++] = t; }
            else if (nums[mid] == 1) mid++;
            else { int t = nums[hi]; nums[hi--] = nums[mid]; nums[mid] = t; }
        }
    }
}

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int lo = 0, mid = 0, hi = (int)nums.size() - 1;   // Dutch national flag
        while (mid <= hi) {
            if (nums[mid] == 0) swap(nums[lo++], nums[mid++]);
            else if (nums[mid] == 1) mid++;
            else swap(nums[mid], nums[hi--]);
        }
    }
};

function sortColors(nums) {
  let lo = 0, mid = 0, hi = nums.length - 1; // Dutch national flag
  while (mid <= hi) {
    if (nums[mid] === 0) { [nums[lo], nums[mid]] = [nums[mid], nums[lo]]; lo++; mid++; }
    else if (nums[mid] === 1) mid++;
    else { [nums[mid], nums[hi]] = [nums[hi], nums[mid]]; hi--; }
  }
}

Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.

Watch the core idea of this problem step by step. Change the input and press Visualize.

Explained in the lesson Sorting Algorithms.