Skip to main content

58. Sort Colors

mediumAsked at Reddit

Sort an array containing only 0s, 1s, and 2s in-place (Dutch national flag). Reddit uses this to test the three-pointer partition — the same shape used when bucketing items into three priority lanes in their ranking pipeline.

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

Source citations

Public interview reports confirming this problem appears in Reddit loops.

  • Glassdoor (2026-Q1)— Reddit phone screen, common interview problem.

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 color 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]

Approaches

1. Two-pass count-sort

Pass 1: count 0s, 1s, 2s. Pass 2: overwrite based on counts.

Time
O(n)
Space
O(1)
function sortColors(nums) {
  let c0 = 0, c1 = 0, c2 = 0;
  for (const x of nums) { if (x === 0) c0++; else if (x === 1) c1++; else c2++; }
  let i = 0;
  while (c0--) nums[i++] = 0;
  while (c1--) nums[i++] = 1;
  while (c2--) nums[i++] = 2;
}

Tradeoff: Two passes. Acceptable but the follow-up wants one pass.

2. Dutch national flag — three pointers (optimal)

lo (< boundary), mid (cursor), hi (> boundary). On 0, swap with lo; on 2, swap with hi; on 1, advance mid.

Time
O(n)
Space
O(1)
function sortColors(nums) {
  let lo = 0, mid = 0, hi = nums.length - 1;
  while (mid <= hi) {
    if (nums[mid] === 0) {
      [nums[lo], nums[mid]] = [nums[mid], nums[lo]];
      lo++; mid++;
    } else if (nums[mid] === 2) {
      [nums[mid], nums[hi]] = [nums[hi], nums[mid]];
      hi--;
    } else {
      mid++;
    }
  }
}

Tradeoff: Single pass. Don't advance mid after swapping with hi (the swapped-in value is unknown).

Reddit-specific tips

Reddit interviewers want the Dutch flag algorithm by name. Bonus signal: state the invariant explicitly — nums[0..lo) all 0, nums[lo..mid) all 1, nums[hi+1..n) all 2; nums[mid..hi] unknown.

Common mistakes

  • Advancing mid after swapping with hi (swapped value is unknown — could be 0).
  • Using <= vs. < incorrectly in the outer loop.
  • Two-pointer (only) version that misses the middle bucket.

Follow-up questions

An interviewer at Reddit may pivot to one of these next:

  • Sort an array with 4+ distinct values.
  • Move zeroes to end (LC 283) — two-pointer.
  • Wiggle Sort (LC 280).

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why don't we advance mid when swapping with hi?

The value that comes in from hi is unknown. After the swap, we still need to inspect nums[mid] in the next iteration.

What if there are more than 3 colors?

Three-pointer generalizes to bucket sort; or use a counting sort for small k.

Practice these live with InterviewChamp.AI

Drill Sort Colors and other Reddit interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →