57. Sort Colors
mediumAsked at DatadogSort 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 Sam K., 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.length1 <= n <= 300nums[i] is either 0, 1, or 2.
Examples
Example 1
nums = [2,0,2,1,1,0][0,0,1,1,2,2]Example 2
nums = [2,0,1][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.
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.