MediumArrayTwo PointersSortingUpdated Sep 2026

75. Sort Colors

Asked at Amazon, Oracle, Walmart

Difficulty

Medium

Time

O(n)

Space

O(1)

Pattern

Array

Companies

3

Problem

You are given an array nums where every element is one of three values: 0, 1, or 2. Think of these as three colors that must appear in this exact order: all 0s first, then all 1s, then all 2s.

Sort the array in place — change the given array itself, do not build a new one. You may not call any built-in sort function.

The follow-up question is the real target: can you do it in one pass over the array, using only constant extra space (a few index variables, no extra array)?

Three values, one required order

nums (input)202110012345The starting array — values are mixed, not grouped.nums (output)001122012345After sorting in place: the 0 zone, then the 1 zone,then the 2 zone.
The input mixes 0s, 1s and 2s; the goal is the same values rearranged as all 0s, then all 1s, then all 2s.

Constraints

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

Examples

Example 1
Inputnums = [2,0,2,1,1,0]
Output[0,0,1,1,2,2]
WhyThe array holds two 0s, two 1s and two 2s. After sorting in place, both 0s come first, then both 1s, then both 2s.
Example 2
Inputnums = [2,0,1]
Output[0,1,2]
WhyThere is one of each value, so the sorted order is simply 0, then 1, then 2.

Asked At

3 companies
CompanyDifficulty
AmazonMediumView all Amazon questions →
OracleMediumView all Oracle questions →
WalmartMediumView all Walmart questions →

How to Think About It

1

Dutch National Flag algorithm: use three pointers — low (boundary for 0s), mid (current element), high (boundary for 2s). One pass through the array.

2

The invariants: everything before low is 0, everything after high is 2, everything between low and mid-1 is 1, everything between mid and high is unexamined.

3

At each step, examine nums[mid]:

  • If 0: swap with nums[low], advance both low and mid.
  • If 1: just advance mid.
  • If 2: swap with nums[high], decrement high (don't advance mid — the swapped element is unexamined).
4

Edge cases: all same color (no swaps needed), empty array, two elements.

Optimal Approach

Step 1: Initialize low = 0, mid = 0, high = n - 1.
Step 2: While mid <= high:

  • If nums[mid] == 0: swap nums[low] and nums[mid]. low++, mid++.
  • If nums[mid] == 1: mid++.
  • If nums[mid] == 2: swap nums[mid] and nums[high]. high--.
    Step 3: The array is sorted in-place.

The key insight: when you swap with high, the swapped element is unexamined, so don't advance mid. When you swap with low, the swapped element (a 1) is already in the right zone, so you can advance.

Time: O(n). Space: O(1).

Dutch flag: three zones grow at once

nums202110012345lowmidhighStart: low = mid = 0, high = 5, nothing is classifiedyet.nums002112012345lowmidhighAfter swapping the 2 at mid with high and then pushingtwo 0s left, the 0 zone and 2 zone are set.nums001122012345midhighmid has passed high, so every element is classifiedand the array is sorted.0: swap(low, mid), low++, mid++1: mid++2: swap(mid, high), high-- (mid stays)
low marks the end of the 0 zone, high marks the start of the 2 zone, and mid scans the unknown middle.
ComplexityTime O(n)Space O(1)Each element is examined at most once by the mid pointer, and only three index variables are stored.

What Trips People Up in Real Interviews

1

Advancing mid after swapping with high. When you swap nums[mid] with nums[high], the element from high is unexamined, so you must NOT advance mid. Only decrement high.

2

Swapping low and mid when nums[mid] == 1. A value of 1 is already in the correct partition (between low and mid). You only advance mid, never swap with low for 1s.

3

Confusing the Dutch National Flag algorithm with simple counting sort. The constraint is to do it in one pass with O(1) space, not two passes with a count array.

4

Forgetting that everything before low is 0, everything after high is 2, and everything between low and mid - 1 is 1. If you lose track of these invariants, the partition breaks.

5

Using four pointers or a hash map instead of the three-pointer low/mid/high approach. The problem explicitly forbids library sort, and a hash map uses extra space.

Solution Code

O(n) time
def sortColors(nums):
    low, mid, high = 0, 0, len(nums) - 1
    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Sort Colors problem?

Given an array nums with n objects colored red, white, or blue (represented as 0, 1, 2), sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue. You must solve it without using the library sort function.

How do you solve Sort Colors?

The optimal approach runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Sort Colors?

Sort Colors is asked at Amazon, Oracle, Walmart. It is a medium difficulty problem.

What are common mistakes on Sort Colors?
  • Advancing `mid` after swapping with `high`. When you swap `nums[mid]` with `nums[high]`, the element from `high` is unexamined, so you must NOT advance `mid`. Only decrement `high`.
  • Swapping `low` and `mid` when `nums[mid] == 1`. A value of 1 is already in the correct partition (between `low` and `mid`). You only advance `mid`, never swap with `low` for 1s.
  • Confusing the Dutch National Flag algorithm with simple counting sort. The constraint is to do it in one pass with `O(1)` space, not two passes with a count array.
  • Forgetting that everything before `low` is 0, everything after `high` is 2, and everything between `low` and `mid - 1` is 1. If you lose track of these invariants, the partition breaks.
  • Using four pointers or a `hash map` instead of the three-pointer `low`/`mid`/`high` approach. The problem explicitly forbids library sort, and a `hash map` uses extra space.