075. Sort Colors

Quick Identifier

Topic: two-pointers
Pattern: Dutch National Flag three-way partition
Difficulty: Medium
Companies: Amazon, Google, Meta, Microsoft, Bloomberg
Frequency: High
LeetCode: 75
Hint: Keep four regions: zeros, ones, unknown, and twos. Only mid inspects unknown values.

Quick Sights

Time Complexity: O(n) - each value is classified once.
Space Complexity: O(1) - swaps are in-place.
Core Mechanism: Use low, mid, and high: send 0 left, keep 1 in the middle, send 2 right.

Concept Explanation

The invariant is the whole algorithm: [0, low) are zeros, [low, mid) are ones, [mid, high] is unknown, and (high, end] are twos.

When mid sees 0, swap it into the zero zone and advance both low and mid. When it sees 1, advance mid. When it sees 2, swap it with high and shrink high; do not advance mid, because the incoming value has not been classified.

Diagram

This diagram shows the pointer decisions and the step-by-step algorithm flow.

Loading diagram…

Study Pattern (SDE3+)

0-3 min: Name the pointer shape, then state the invariant and discard rule before coding.
Implementation pass: Keep pointer movement explicit; every branch must return, record an answer, or move at least one pointer.
5 min extension: Explain how the solution changes for immutable input, streaming input, many duplicate values, or many repeated queries.

Approaches

Counting values is two passes. Built-in sort is O(n log n). Dutch National Flag is one pass and constant space.

Optimal Solution

JavaScript

function sortColors(nums) {
	let low = 0, mid = 0, high = nums.length - 1;
	while (mid <= high) {
		if (nums[mid] === 0) {
			[nums[low], nums[mid]] = [nums[mid], nums[low]];
			low++; mid++;
		} else if (nums[mid] === 1) mid++;
		else {
			[nums[mid], nums[high]] = [nums[high], nums[mid]];
			high--;
		}
	}
}

Go

func sortColors(nums []int) {
	low, mid, high := 0, 0, len(nums)-1
	for mid <= high {
		switch nums[mid] {
		case 0:
			nums[low], nums[mid] = nums[mid], nums[low]
			low++
			mid++
		case 1:
			mid++
		case 2:
			nums[mid], nums[high] = nums[high], nums[mid]
			high--
		}
	}
}