Skip to main content

57. Sort Colors

mediumAsked at Datadog

Sort an array of 0s, 1s, and 2s in place in one pass. Datadog asks this as the canonical Dutch National Flag warmup — same three-way-partition trick they use for tagging metric series by priority.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite — graded on Dutch National Flag.
  • Blind (2025-11)— Recurring at Datadog.

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. Counting sort (two passes)

Count 0s, 1s, 2s; rewrite array in order.

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

Tradeoff: Two passes. Datadog explicitly asks for one pass.

2. Dutch National Flag three-pointer (optimal)

Three pointers: lo (next 0 slot), hi (next 2 slot), i (current scan). Move 0s left, 2s right, 1s stay.

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

Tradeoff: One pass, O(1) extra space. The three-pointer dance is the Datadog-canonical pattern for in-place three-way partition.

Datadog-specific tips

Datadog grades on whether you DON'T advance i when swapping with hi. The reason: the value just swapped INTO position i is unknown (could be 0, 1, or 2). Articulate this before coding.

Common mistakes

  • Advancing i after swapping with hi — would skip checking the newly-arrived value.
  • Advancing i after swapping with lo — wait, this IS correct, because the value swapped into i came from before lo, which was known to be 0 or 1 (and 1 would have already been handled).
  • Using strict < instead of <= in the loop — terminates one element early.

Follow-up questions

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

  • Sort Colors with K colors — generalized Dutch flag.
  • Wiggle Sort — different partitioning.
  • Datadog-style: tag metric series into priority buckets in one pass.

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 advance i on a 0-swap but not on a 2-swap?

The value swapped INTO position i from lo was either 0 or 1 (anything before lo is 0 or 1 by invariant). So after a 0-swap, i is safe to advance. After a 2-swap, the value from hi could be anything, so we re-check.

Why is the loop condition i <= hi?

hi shrinks as we push 2s to the right. We need to process everything up to and including hi.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →