Sort Colors LeetCode Solution (Medium) (2026)

Approach Summary

Dutch National Flag algorithm: three-way partition with lo, mid, hi pointers. Swap to move 0s left, 2s right.

Practice Mode

Solve it yourself before revealing the code

DSA interviews test reasoning from brute force to optimal. Think through the constraints first.

Full Solution & Approach

The array contains only three distinct values — 0, 1, 2 — so a counting sort is allowed, but the problem explicitly asks for a one-pass in-place solution, which is the Dutch National Flag algorithm. Maintain three regions with three pointers: everything before lo is 0, everything after hi is 2, and mid scans the middle. While mid does not pass hi, inspect nums[mid]. If it is 0, swap it with nums[lo] and advance both lo and mid — a 0 has been locked into the left region. If it is 1, it is already in the correct region, so just advance mid. If it is 2, swap it with nums[hi] and decrement hi, but do NOT advance mid — the value swapped into mid from the right region is unexamined and must be processed on the next iteration. The three regions never overlap and every swap places at least one element in its final region, so the loop runs in O(n) with only constant extra space. The pattern generalizes to any k-way partitioning and is the canonical implementation of the quick-sort three-way partition used to sort arrays with many duplicate keys.

Each iteration either advances mid or shrinks the hi region, so the loop runs at most n times — O(n) time. Only three index variables, so O(1) space.

Solution Code

Solution

public void sortColors(int[] nums) {
    int lo = 0, mid = 0, hi = nums.length - 1;
    while (mid <= hi) {
        if (nums[mid] == 0) {
            int tmp = nums[lo]; nums[lo] = nums[mid]; nums[mid] = tmp;
            lo++; mid++;
        } else if (nums[mid] == 1) {
            mid++;
        } else {
            int tmp = nums[mid]; nums[mid] = nums[hi]; nums[hi] = tmp;
            hi--;
        }
    }
}

void sortColors(vector<int>& nums) {
    int lo = 0, mid = 0, hi = (int)nums.size() - 1;
    while (mid <= hi) {
        if (nums[mid] == 0) {
            swap(nums[lo], nums[mid]);
            lo++; mid++;
        } else if (nums[mid] == 1) {
            mid++;
        } else {
            swap(nums[mid], nums[hi]);
            hi--;
        }
    }
}

def sort_colors(nums: list[int]) -> None:
    lo, mid, hi = 0, 0, len(nums) - 1
    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

function sortColors(nums) {
  let lo = 0, mid = 0, hi = nums.length - 1;
  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--;
    }
  }
}

Edge Cases to Watch

All zeros or all twos — the pointer regions still partition correctly
Single element — no swaps needed
Already sorted — the algorithm still makes a full pass
Mixed pattern like 2,0,2,1,1,0 — the mid-not-advancing step after a 2-swap is what makes it correct

Algorithmic Pattern

Master the Two Pointers Pattern

View Pattern Guide →

Study the core invariant, step-by-step decision framework, and common interview traps for the Two Pointers pattern.

Framework: Two Pointers • Interview Prep: Tested at FAANG • Explore all Two Pointers problems & invariants →

How to Recognize This Pattern

In-place sort of array with only 3 distinct values
"Sort 0s, 1s, 2s in one pass"

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(1)

Frequently Asked Questions

What is the optimal time and space complexity for Sort Colors?

The optimal solution for Sort Colors achieves O(n) runtime complexity and requires O(1) auxiliary space. Each iteration either advances mid or shrinks the hi region, so the loop runs at most n times — O(n) time. Only three index variables, so O(1) space.

How do I identify that Sort Colors requires the Two Pointers pattern?

In technical interviews, look for key problem signals: In-place sort of array with only 3 distinct values; "Sort 0s, 1s, 2s in one pass". Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Two Pointers strategy.

What critical edge cases must be handled in Sort Colors?

Essential edge cases to verify include: All zeros or all twos — the pointer regions still partition correctly; Single element — no swaps needed; Already sorted — the algorithm still makes a full pass; Mixed pattern like 2,0,2,1,1,0 — the mid-not-advancing step after a 2-swap is what makes it correct. Always walk through these scenarios with your interviewer before coding.

Which tech companies frequently ask Sort Colors?

Sort Colors is a Medium-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Facebook, Microsoft, Amazon.

Sort Colors LeetCode Solution