Skip to main content

57. Sort Colors

mediumAsked at Vercel

Sort an array of 0s, 1s, and 2s in one pass without extra space (Dutch National Flag). Vercel asks this for the three-pointer partitioning — same shape as their priority-bucket scheduler for request fan-out.

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

Source citations

Public interview reports confirming this problem appears in Vercel loops.

  • Glassdoor (2025-Q4)— Vercel platform onsite; three-pointer expected.
  • Blind (2026-Q1)— Listed in Vercel runtime engineer screen.

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 (two pass)

Count 0s, 1s, 2s; overwrite the array in order.

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

Tradeoff: Two passes; works but Vercel asks for one-pass.

2. Dutch National Flag (one pass, optimal)

Three pointers: lo (next slot for 0), mid (current), hi (next slot for 2). If nums[mid] == 0, swap with lo and advance both. If == 2, swap with hi and decrement hi (don't advance mid). 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. Key insight: don't advance mid after a 2-swap because the swapped-in value at mid is unknown — must re-examine.

Vercel-specific tips

Vercel grades the one-pass Dutch National Flag. Bonus signal: explaining WHY you don't advance mid after swapping with hi (the value coming from hi is unprocessed; the value coming from lo is known to be a 1 because it was already in the 1-zone). Mention that this generalizes to k-way partitioning.

Common mistakes

  • Advancing mid after a 2-swap — corrupts because hi's value is unprocessed.
  • Off-by-one on the while loop: mid < hi vs mid <= hi — must be <=.
  • Forgetting that swapping with lo advances both (because lo's value is a known 1).

Follow-up questions

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

  • k-way partitioning — variant with more colors.
  • Sort an array of arbitrary values into <pivot, =pivot, >pivot (quicksort partition).
  • Sort 0s, 1s, 2s in a linked list.

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 doesn't mid advance after a 2-swap?

The value coming from hi is one we haven't processed — could be 0, 1, or 2. We need to re-check it at the same mid position before moving on.

Why DOES mid advance after a 0-swap?

The value coming from lo is guaranteed to be a 1 (lo points to the next slot for 0, but it's currently holding a 1 — because all positions before mid are sorted). So we can safely advance both.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →