Sort Colors

Problem Description

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library’s sort function.

Examples

Constraints

• n == nums.length
• 1 <= n <= 300
• nums[i] is either 0, 1, or 2.

Dutch National Flag Partitioning

While counting the occurrences of 0, 1, and 2 and overwriting the array is a valid two-pass solution, you can sort it in a single pass using the Dutch National Flag algorithm. Maintain three pointers: low (boundary of 0s), mid (current scan pointer), and high (boundary of 2s). When you see a 0, swap it with the element at low and increment both low and mid. When you see a 2, swap it with the element at high and decrement high (do not increment mid since the swapped element needs to be processed). When you see a 1, simply advance mid.

Solution 1: Dutch National Flag Algorithm

Single-pass three-pointer array partitioning.

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);
                low++;
                mid++;
            } else if (nums[mid] == 1) {
                mid++;
            } else {
                swap(nums, mid, high);
                high--;
            }
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

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

#include <vector>
#include <utility>

class Solution {
public:
    void sortColors(std::vector<int>& nums) {
        int low = 0, mid = 0, high = nums.size() - 1;
        while (mid <= high) {
            if (nums[mid] == 0) {
                std::swap(nums[low], nums[mid]);
                low++;
                mid++;
            } else if (nums[mid] == 1) {
                mid++;
            } else {
                std::swap(nums[mid], nums[high]);
                high--;
            }
        }
    }
};

Complexity Analysis

• Time Complexity: O(n) since we iterate through the array at most once.
• Space Complexity: O(1) auxiliary space as the sorting is done in-place with three pointers.

Where It Breaks

This partitioning scheme is specialized for 3 distinct values (categories). If there are more than 3 classes to sort, standard quicksort or counting sort must be used instead.

Common Mistakes

• Incorrect pointer advancement: Incrementing mid after swapping with high. Since the element swapped from high is unexamined, it must be evaluated at the current mid index.
• Loop termination: Ending the loop at mid < high instead of mid <= high, which misses processing the element at the boundary index.

Frequently Asked Questions

Why does this problem matter in interviews? It tests your ability to partition arrays in place without allocating auxiliary hash maps or temporary counting arrays.

Can we solve this using counting sort? Yes. You can count the frequency of 0s, 1s, and 2s in one pass, then fill the array. That is a two-pass solution, whereas the Dutch National Flag is a one-pass solution.

← All Problems