MediumTwo Pointers

Sort Colors

Explanation & Solution

Description

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

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

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

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

Explanation: The array is sorted so that all 0s (red) come first, then all 1s (white), then all 2s (blue).

Constraints

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

Approach

Two Pointers pattern

1. Initialize Three Pointers

Set low = 0 — boundary for the next 0 placement
Set mid = 0 — current element being examined
Set high = nums.length - 1 — boundary for the next 2 placement
The goal is to partition the array into three regions: [0..low-1] are 0s, [low..mid-1] are 1s, and [high+1..end] are 2s

2. Loop While mid <= high

Continue processing until mid crosses high
Everything from mid to high is still unexamined

3. Current Element Is 0 — Swap With Low

If nums[mid] === 0, swap nums[mid] with nums[low]
Increment both low and mid
The element swapped from low is guaranteed to be a 1 (or mid itself if low === mid), so it is safe to advance mid

4. Current Element Is 1 — Skip

If nums[mid] === 1, simply increment mid
1s naturally accumulate in the middle section between low and mid

5. Current Element Is 2 — Swap With High

If nums[mid] === 2, swap nums[mid] with nums[high]
Decrement high only — do not increment mid
The swapped-in element from high is unknown and must be examined in the next iteration

6. Return the Modified Array

When mid > high, every element has been placed in its correct partition
The array is now sorted as [0, 0, ..., 1, 1, ..., 2, 2, ...]

Key Insight

This is the Dutch National Flag algorithm, designed by Edsger Dijkstra. The three pointers maintain an invariant that partitions the array into four regions (0s, 1s, unprocessed, 2s), and each swap moves one element into its final region

Time

O(n)each element is visited at most twice

Space

O(1)sorting is done in-place with only three pointer variables

Visualization

Input:

[2, 0, 2, 1, 1, 0]

—

Press ▶ or use ← → to step through

LowMidHighSorted

9 steps

Solution Code

Container With Most Water

Remove Element