Skip to main content

59. Sort Colors

mediumAsked at Snowflake

Sort an array of three values (0, 1, 2) in one pass. Snowflake asks this for the Dutch-National-Flag three-pointer technique — directly relevant to in-place partitioning during their executor's range repartition.

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

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2025-Q4)— Snowflake execution-engine team uses this in onsites.
  • LeetCode Discuss (2025-09)— Reported at Snowflake new-grad screens.

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 passes)

Count 0s, 1s, 2s. Write back.

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

Tradeoff: Two passes. Fine, but misses the follow-up of one-pass.

2. Dutch National Flag — three pointers (optimal)

low (boundary of 0s), mid (cursor), high (boundary of 2s). At each step: if nums[mid] == 0, swap with low and advance both; if 2, swap with high and advance only high; if 1, advance mid.

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

Tradeoff: Single pass, O(1) state. The invariant: nums[0..low-1] = 0; nums[low..mid-1] = 1; nums[high+1..n-1] = 2.

Snowflake-specific tips

Snowflake interviewers want the three-pointer version and the invariant stated. Bonus signal: connect to in-place range partitioning during repartition — when Snowflake redistributes rows across compute nodes by range, it uses a similar in-place three-way (or k-way) partitioning to avoid extra memory allocations.

Common mistakes

  • Advancing mid after swapping with high — the swapped-in value hasn't been examined yet, must re-process.
  • Off-by-one with high (must be inclusive: while mid <= high, not <).
  • Using two pointers (Lomuto-style) — works for 0s and rest, but a second pass for 1s and 2s is needed.

Follow-up questions

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

  • k colors (k-way Dutch flag).
  • Sort an array of three distinct values in a stream.
  • How does Snowflake repartition rows in-place during shuffle?

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 not advance mid after swapping with high?

The element that was at high (now at mid) is unknown — could be 0, 1, or 2. You need to re-process it. Don't advance mid yet.

What invariant do the three pointers maintain?

nums[0..low-1] are 0s, nums[low..mid-1] are 1s, nums[high+1..end] are 2s. nums[mid..high] is the unprocessed window.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →