Skip to main content

75. Sort Colors

medium

Sort an array of 0s, 1s, and 2s in-place without using any sort library. The Dutch National Flag problem — three pointers, one pass, O(1) space.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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 will use the integers 0, 1, and 2 to represent the colors red, white, and blue respectively. You must solve this problem without using the library's sort function.

Constraints

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

Examples

Example 1

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

Example 2

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

Example 3

Input
nums = [0]
Output
[0]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

A counting-sort two-pass solution is simple — count zeros, ones, twos, then overwrite. Can you do it in a single pass?

Hint 2

Maintain three pointers: low (next slot for 0), mid (current scanner), and high (next slot for 2).

Hint 3

When nums[mid] is 0, swap with low and advance both. When 2, swap with high and decrement high (don't advance mid, the swapped-in value is unverified). When 1, just advance mid.

Solution approach

Reveal approach

Dutch National Flag algorithm with three pointers. Initialize low = 0, mid = 0, high = n - 1. While mid <= high, look at nums[mid]: if it is 0, swap nums[low] and nums[mid], then increment both low and mid. If it is 2, swap nums[mid] and nums[high], then decrement high but leave mid (the value swapped in from high has not been classified yet). If it is 1, just increment mid. The invariants are: everything left of low is 0, everything between low and mid is 1, everything right of high is 2, and mid..high is the unprocessed region. One pass, in place, no auxiliary structures.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • three-pointers
  • in-place
  • partition

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Google
  • Apple
  • Meta

Practice these live with InterviewChamp.AI

Drill Sort Colors and Arrays problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →