Faangprep Logo
LoginRegister
Two Pointers
Medium

Sort Colors

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 use the integers `0`, `1`, and `2` to represent the color red, white, and blue, respectively.
10 min read
Solve on LeetCode
Problem Understanding

The Goal

We need to sort an array containing only 0s, 1s, and 2s. The catch is that we must do this in-place (without creating a new array) and ideally in one pass (O(n) time).

  • 0: Represents Red (should be at the beginning)
  • 1: Represents White (should be in the middle)
  • 2: Represents Blue (should be at the end)

Input/Output Examples

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

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

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

  • Output: [0, 1, 2]

Constraints

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

[!IMPORTANT]
A simple solution would be to count the number of 0s, 1s, and 2s, and then overwrite the array. However, the "Dutch National Flag" algorithm allows us to do this in a single pass with constant space.

Algorithm Strategy

The Dutch National Flag Algorithm

This problem is a classic variation of the Dutch National Flag problem proposed by Edsger Dijkstra. We use three pointers to partition the array into three sections:

  1. low: The boundary for 0s (Red). Everything before low is 0.
  2. high: The boundary for 2s (Blue). Everything after high is 2.
  3. mid: The current element iterator. Everything between low and mid is 1 (White).

The Logic

We iterate with the mid pointer and check nums[mid]:

  1. If nums[mid] == 0:
    • This belongs in the "0 zone" (at the start).
    • Swap nums[mid] with nums[low].
    • Increment both low and mid.
  2. If nums[mid] == 1:
    • This belongs in the middle. It's already in the right relative place.
    • Just increment mid.
  3. If nums[mid] == 2:
    • This belongs in the "2 zone" (at the end).
    • Swap nums[mid] with nums[high].
    • Decrement high.
    • Crucial: Do NOT increment mid yet! The element we just swapped from high to mid hasn't been checked. We need to process it in the next iteration.

Visualizing the Zones

[0, 0, ... 0    1, 1, ... 1    ?, ?, ... ?    2, 2, ... 2]
^              ^              ^              ^
0             low            mid            high
Visualization
Step 1 / 14
low
mid
2
0
0
1
2
2
1
3
1
4
high
0
5

Initial State. We use three pointers: 'low' for 0s, 'mid' for 1s, and 'high' for 2s.

1x
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.
Unlock VisualizerPREMIUM FEATURE

Stop Guessing, Start Mastering.

Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.

Start Your Premium Prep