How do you approach Sort Colors?

Can you solve this in a single pass through the array?

What is the time complexity of Sort Colors?

Time complexity: O(n) - single pass. Space complexity: O(1) - in-place.

What are common mistakes on Sort Colors?

Forgetting the input has to be sorted. If it is not, the pointer moves mean nothing and the answer only looks right on the sample. Moving both pointers on a match when only one should move, which steps over valid pairs. Choosing left < right where left <= right is meant. The first never examines the middle element.

Sitelet https://gitgood.dev/coding/sort-colors

gitGood.dev

← Back to problems

Sort Colors

MediumAlgorithms

Description

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 color red, white, and blue, respectively.

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

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]

Constraints

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

Sort Colors: approach, complexity and pitfalls

A medium two pointers problem, graded against 6 test cases (3 of them hidden).

The pattern: Two Pointers

Two indices walking a sorted array or string, usually from opposite ends.

Reach for it when you see: A sorted input, a palindrome check, or a pair/triplet that must satisfy a condition.

If you are stuck

Show the 3-step hint ladder

Can you solve this in a single pass through the array?
Use three pointers: one for the next position of 0, one for current element, and one for the next position of 2.
This is known as the Dutch National Flag problem.

The optimal approach

Show the approach: Dutch National Flag (Three Pointers)

Use three pointers: `low` (next position for 0), `mid` (current), and `high` (next position for 2). Swap elements to their correct regions in a single pass.

Time: O(n) - single pass
Space: O(1) - in-place

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Two Pointers mistakes

These apply to the pattern as a whole, not just this problem.

Forgetting the input has to be sorted. If it is not, the pointer moves mean nothing and the answer only looks right on the sample.
Moving both pointers on a match when only one should move, which steps over valid pairs.
Choosing `left < right` where `left <= right` is meant. The first never examines the middle element.