Skip to main content

57. Sort Colors

mediumAsked at Plaid

Sort an array of 0s, 1s, and 2s in place in one pass. Plaid asks this because partitioning a transaction stream into 'pending', 'cleared', 'failed' buckets uses exactly this Dutch National Flag primitive.

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

Source citations

Public interview reports confirming this problem appears in Plaid loops.

  • Glassdoor (2025)— Plaid SWE II OA.
  • LeetCode Discuss (2026)— Plaid Dutch National Flag classic.

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 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. Counting sort

Count each color, then overwrite.

Time
O(n)
Space
O(1)
function sortColors(nums) {
  const c = [0, 0, 0];
  for (const n of nums) c[n]++;
  let i = 0;
  for (let k = 0; k < 3; k++) for (let j = 0; j < c[k]; j++) nums[i++] = k;
}

Tradeoff: Two passes. Acceptable but the prompt hints at one pass.

2. Dutch National Flag (three pointers)

lo points at the first unsorted position, hi at the last. mid scans. If mid is 0, swap with lo. If 2, swap with hi. If 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, in-place. The key subtlety: after swapping with lo, we advance both because the swapped-in element is known to be 1 (since lo was at a 1). After swapping with hi, we don't advance mid because the swapped-in element from hi is unknown.

Plaid-specific tips

Plaid grades this on the asymmetric pointer-advancement rule, which trips most candidates. Bonus signal: connect to transaction-status partitioning where pending/cleared/failed must end up grouped in a single in-place pass.

Common mistakes

  • Advancing mid after swapping with hi — leaves an unchecked element behind.
  • Using mid < hi instead of mid <= hi — misses the last element.
  • Adding extra branches for nums[mid] not in {0, 1, 2} — unnecessary for the spec.

Follow-up questions

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

  • Sort an array of k colors (rainbow sort).
  • Partition around a pivot (used in quickselect).
  • Sort transactions by status with a stability requirement.

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 after the hi swap?

The element swapped in from hi is unknown — could be 0, 1, or 2. We need to re-examine it.

Why do we advance mid after the lo swap?

Before the swap, nums[lo] was in the 'middle band' which by invariant means it's a 1 (lo points at the first non-zero). So the swapped-in element is a 1 and doesn't need re-checking.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →