Skip to main content

56. Sort Colors

mediumAsked at Workday

Sort an array of 0s, 1s, and 2s in one pass. Workday uses this for Dutch-national-flag fluency — same shape as bucketing employees into three pay-grade tiers in one pass.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2025)— Workday compensation-bucketing variant.

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.
  • Follow-up: Could you come up with a one-pass algorithm using only constant extra space?

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 zeros, ones, twos. Write back.

Time
O(n)
Space
O(1)
let c=[0,0,0]; for (const x of nums) c[x]++;
let i=0; for (let k=0;k<3;k++) while (c[k]--) nums[i++]=k;

Tradeoff: Two passes. Fine but the follow-up asks for one.

2. Dutch national flag (one pass, 3 pointers)

lo, mid, hi. nums[mid]==0 swap lo/mid, advance both. ==2 swap mid/hi, decrement hi. ==1 just 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--;
      // don't advance mid — could be another 2 or 0
    } else {
      mid++;
    }
  }
}

Tradeoff: Single pass. The non-advance of mid on swap-with-hi is the trick — the swapped-in value is unprocessed.

Workday-specific tips

Workday wants the one-pass Dutch flag. The non-advance of mid after the hi-swap is the part candidates miss — articulate this before coding (swapped-in value from hi is unprocessed, mid must re-check).

Common mistakes

  • Advancing mid after swapping with hi — skips processing the swapped-in value.
  • Using mid < hi instead of mid <= hi — misses the final element.
  • Three separate passes when one suffices.

Follow-up questions

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

  • Sort an array of k distinct values — multi-pointer.
  • Wiggle Sort (LC 280).
  • What if there are 4 colors?

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 swap with hi?

We swapped in a value from the right side that we haven't seen yet. It could be a 0 or 2 or 1 — must process before advancing.

Why does mid advance after swap with lo?

lo always holds a 1 (because mid passed it earlier without swapping). Swapping in a 1 from lo means we know what we have — advance both pointers.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →