sort-colors

Difficulty: Medium  ·  Topic: Two Pointers  ·  Practice it on parikshan: /practice/sort-colors/start

The story

Slack's message backfill job ingests a giant batch of historical messages from a deprecated message bus. Each record carries a coarse priority bucket: 0 for system-broadcast, 1 for normal-user-traffic, 2 for bot-noise. The reindex pipeline needs the batch sorted by bucket before it hands it to Elasticsearch, but cannot afford the log-linear cost of a general sort over a 100M-record batch. Buckets are only three values, the count is known to be in the millions, and the batch must stay in place because the buffer is mmap'd from disk and you cannot afford to allocate a parallel copy.

That is sort-colors, the canonical Dutch National Flag problem. Three pointers partition the array into three regions in one pass, with O(1) extra memory.

What's actually being asked

Given an array nums of length n whose elements are each 0, 1, or 2, sort it so all 0s come first, then all 1s, then all 2s. Single pass, O(1) extra space.

The naive approach

Two options that both pass the tests but miss the lesson:

• nums.sort(). O(n log n). Wrong scaling.
• Counting sort: count zeros, ones, twos; overwrite the array. O(n) time, O(1) space, but it makes two passes over the array.

The single-pass O(1)-space answer is the Dutch National Flag partition. It is the one the interview rewards and the one production systems actually use because the second pass touches memory you have already evicted from cache.

The key insight

Maintain three regions, parameterised by three pointers:

• [0, lo), already known to be all 0s.
• [lo, mid), already known to be all 1s.
• (hi, n - 1], already known to be all 2s.
• [mid, hi], unprocessed.

Look at nums[mid]:

• If 0: it belongs in the front region. Swap with nums[lo] (which is a known 1 or the same index as mid when lo == mid), then advance both lo and mid. Why both? Because the swap pulled in a known 1 (or the same 0, on the first iteration) into the middle region, which is already classified.
• If 1: it is already in its correct region. Advance mid only.
• If 2: it belongs in the back region. Swap with nums[hi]. Decrement hi. Do not advance mid, the value pulled in from the back is unprocessed; you have to classify it on the next iteration.

The loop runs while mid <= hi. When mid > hi, the unprocessed region is empty and the partition is complete.

Step-by-step approach

1. Set lo = 0, mid = 0, hi = n - 1.
2. While mid <= hi:
   • If nums[mid] == 0: swap nums[lo] and nums[mid]; lo += 1; mid += 1.
   • Elif nums[mid] == 1: mid += 1.
   • Else (nums[mid] == 2): swap nums[mid] and nums[hi]; hi -= 1.
3. Print nums as space-separated values.

Worked example

nums = [2, 0, 2, 1, 1, 0]
n = 6

Now mid = 4 > hi = 3, exit. Output: 0 0 1 1 2 2.

Complexity

• Time: O(n). Each pointer crosses the array at most once.
• Space: O(1).

This dominates counting sort because it is a single pass and dominates comparison sort because it is linear.

Common pitfalls

• Advancing mid on a 2 swap. The classic bug. The value pulled in from hi is unclassified; advancing mid skips it. Test on [2, 0, 2, 1, 1, 0], if you advance, the second 2 ends up in the wrong place.
• Not advancing mid on a 0 swap. The value pulled in from lo is a known 1 (or the same 0 when lo == mid); it is already in the middle region and should be passed over. If you don't advance, you re-process it and break the invariant.
• Looping while mid < hi instead of mid <= hi. You miss the final index when mid == hi.
• Using a 4-way partition or a counter dictionary. Overkill; both add constant memory and lose the single-pass elegance.
• Sorting in place with sort(). Correct, but O(n log n), wrong scaling and wrong skill.

Where this shows up in the enterprise

• Slack message backfill: partition by coarse priority bucket in place.
• AWS Lambda dispatch: partition concurrent invocation records by SLA tier before round-robin assignment.
• Tesla Autopilot scene parsing: classify objects into three urgency tiers (immediate brake, attention, ignore) in place on the sensor buffer.
• Stripe Radar: triage events into pass / review / block tiers in a fixed-size buffer.
• Cloudflare WAF: bucket requests into allow / challenge / block before the next pipeline stage.
• Netflix encoder farm: partition jobs by priority (live / vod / batch) on a shared queue without extra allocation.
• GitHub Actions runners: scheduler partitions queued workflows into three SLAs before dispatch.
• Bloomberg trade ticker: partition incoming ticks into three feeds (real-time / consolidated / delayed) in a shared buffer.

The pattern is: three known classes, single in-place partition, no extra memory. Dutch National Flag is the standard answer.

Variants you'll see elsewhere

• partition-array: two-way partition around a pivot (the QuickSort partition step). Same skeleton, two pointers instead of three.
• wiggle-sort: more complex partition with three regions and parity constraints.
• sort-array-by-parity-ii: two-way partition with index-parity constraints.
• kth-largest-element: uses QuickSelect, which is a two-way partition driven by a random pivot.
• dutch-national-flag (full): the literal name of this algorithm, attributed to Edsger Dijkstra.

How parikshan turns this into a learning loop

After you read this article and click through to the practice link, the parikshan flow integrates four layers:

1. The editor runs your code against public tests for instant feedback and against per-session dynamic private tests (generated freshly per session). Synthetic cases include all-same arrays (a single class), already-sorted, reverse-sorted, single-element, and arrays where one of the three classes is absent.
2. Hints are graduated. Level 2 specifically describes the three-region invariant. Level 4 gives you the full mid-vs-2 rule that catches everyone the first time.
3. The AI training assistant in exam mode offers Explain, Review, Find Bugs, Add Comments, Optimise, each at an integrity cost. In practice mode AI chat is free; it is the right place to ask "why don't I advance mid on a 2?".
4. The dispute flow runs after the verdict. The most common dispute on this problem: "my counting sort is correct". It is, the spec just rewards the harder, more useful pattern.

Read this concept, attempt in practice mode, take a hint when truly stuck, then redo in exam mode. When you can write the three-pointer partition without looking, including the asymmetric advance rule for 2, the pattern is yours.

In the AI-integrated workspace

In your future job, the agent writes the code. Your job is to:

1. Recognise three-class partition any time you see "K distinct values, sort in place, single pass". The recognition is the skill.
2. Tell the agent precisely: "Dutch National Flag, three pointers, do not advance mid on the 2 swap". The last clause is the load-bearing one; skip it and the agent will write a subtly wrong version that passes the public tests and fails on private cases.
3. Read the generated code and verify: (a) the loop bound is mid <= hi, (b) the 2 branch does not advance mid, (c) 0 advances both lo and mid, (d) the array is mutated in place.
4. Push the edge cases the agent will miss: one class absent (e.g. all 1s), two classes only, already sorted, reverse sorted, single element.

Candidates who can name "Dutch National Flag" within five seconds are the ones who turn agents into leverage. Candidates who can't end up reviewing 60 lines of generated counting-sort and approving it because the public tests pass. parikshan is built to train the first kind.