075. Sort Colors

At a Glance

Topic: two-pointers
Pattern: Dutch National Flag (three-way partition)
Difficulty: Medium
Companies: Amazon, Google, Meta, Microsoft, Bloomberg
Frequency: High
LeetCode: 75

Problem (one-liner)

Given an array of n objects colored red (0), white (1), or blue (2), sort them in-place so objects of the same color are adjacent in red-white-blue order.

Recognition Cues

"Sort array of 0,1,2" or Dutch flag
"Single pass" / constant extra space
Three buckets with two boundaries

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Brute force — count occurrences then overwrite — O(n) time / O(1) space — two passes.
Better — sort built-in — O(n log n) — violates spirit if asked for linear.
Optimal — three pointers (low, mid, high) — O(n) time / O(1) space — one pass partition.

Optimal Solution

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--
		}
	}
}

JavaScript

function sortColors(nums) {
	let low = 0;
	let mid = 0;
	let 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--;
		}
	}
}