In a three-way Dutch national flag partition, why must mid not advance after a swap with the high region?
answer
- three pointers, but four regions
- name what the span between mid and high means
- one swap brings back a scanned element
- the other brings back an untested one
- only the untested case holds mid still
basics
~20 sBecause the record swapped in from the high end has never been examined. A low-side swap brings back an element already scanned and classified, so mid may advance; skipping the newly arrived one would file it in the wrong region.
solid answer
~40 sThe pass keeps four regions: `[0, low)` already classified as the first category, `[low, mid)` as the second, `[mid, high]` still unexamined, and `(high, n)` as the third. When the element at `mid` belongs in the first category you swap it with `low`, and because everything in `[low, mid)` is second-category and already scanned, the incoming element is known — so both `low` and `mid` advance. When it belongs in the third category you swap it with `high`, and `high` sits inside the *unexamined* region, so the incoming element has never been tested. Advancing `mid` there would push an unclassified record behind the frontier and leave it misfiled. Instead only `high` shrinks. Termination still holds: every iteration either advances `mid` or decreases `high`, so the unexamined region loses one element each time.
code
pseudocode · 14 lines// severities: CRITICAL, MAJOR, MINOR
low = 0
mid = 0
high = length(q) - 1
while mid <= high:
if q[mid] == CRITICAL:
swap(q[low], q[mid])
low = low + 1
mid = mid + 1
else if q[mid] == MAJOR:
mid = mid + 1
else:
swap(q[mid], q[high])
high = high - 1go deeper
Be ready to name the three pointers and say which category each of the four regions holds. Knowing that one span is deliberately unexamined is most of the answer.
Explain the asymmetry out loud: a low-side swap returns a scanned element, a high-side swap returns an untested one. Then show the pass terminates because the unexamined span shrinks every iteration.
Demonstrate how you would catch this in review or in tests — inputs with all three categories interleaved, and an assertion on region boundaries rather than on a spot-checked output.
Judge when the one-pass in-place regrouping is worth its subtlety at all, versus a clearer two-pass or bucketed approach that a whole team can maintain without re-deriving the invariant.
## The setting Imagine an in-memory incident queue where each record carries a severity of **critical**, **major** or **minor**, and you want the queue regrouped in place so the triage tooling can walk a contiguous critical block, then the majors, then the minors — one pass, no second queue, no sort. This is the three-way partition usually named after Dijkstra's Dutch national flag problem, and its whole difficulty lives in one pointer-update rule. ## Four regions, three pointers The pass maintains `low`, `mid` and `high` and the following invariant at the top of every iteration, for a queue `q` of `n` records: | Range | Meaning | |---|---| | `q[0 .. low-1]` | classified critical | | `q[low .. mid-1]` | classified major | | `q[mid .. high]` | **not yet examined** | | `q[high+1 .. n-1]` | classified minor | The unexamined region is the one that matters. It is bounded on the left by `mid` and on the right by `high`, and the loop runs while `mid <= high` — that is, for exactly as long as something remains unexamined. ## Why the two swaps are not symmetric When `q[mid]` is **critical**, you swap it with `q[low]`. What comes back? Position `low` is the first slot of the major region, so the element arriving at `mid` is a major — already scanned, already classified. (When `low == mid` the swap is with itself, which is also harmless.) Since the incoming element needs no further examination, `mid` advances along with `low`, and the major region simply slides right by one. When `q[mid]` is **minor**, you swap it with `q[high]`. Position `high` is the *last slot of the unexamined region*. The element arriving at `mid` has never been tested — it could be critical, major or minor. If you advance `mid` anyway, that record silently joins the major region without anyone having looked at it. A critical incident ends up filed between the majors, and the bug survives most small tests because the wrong record is often a major by luck. So on this branch only `high` decreases, and the very next iteration re-examines the same `mid` position with its new occupant. That asymmetry — advance on the low-side swap, hold on the high-side swap — is the single fact this pattern is asked about. ## Termination and the loop bound There is no risk of looping forever: the middle branch advances `mid`, the low branch advances `mid`, and the high branch decreases `high`, so the quantity `high - mid` strictly decreases every iteration. The pass therefore performs at most `n` iterations and runs in `O(n)` time with `O(1)` extra space, comparing each record once or twice. The companion bug is the loop condition. Writing `while mid < high` stops with `mid == high`, one record still unexamined and sitting in the unclassified gap between the major and minor regions. It stays wherever it happened to be, so the output looks right whenever that last record happens to be a major and wrong otherwise — a textbook flaky-looking bug with an entirely deterministic cause. Use `mid <= high`. ## Why three regions instead of two passes You can always regroup three categories with two two-way passes, or by counting each category and rewriting the queue. The three-way pass earns its keep when the elements are *records* rather than plain keys — counting and rewriting means reconstructing records, while swapping moves them. It also finishes in one traversal, which matters when the collection is large enough that a second pass costs real memory traffic. The price is a fiddlier invariant, which is exactly why interviewers ask about it: the pattern is small enough to write on a whiteboard and subtle enough that the pointer rule separates people who have reasoned about the invariant from people who have memorised a shape. ## Tracing it The cheapest way to convince yourself is to trace four records — say major, minor, critical, minor — and watch `q[mid .. high]` shrink by exactly one each iteration while every element leaving that window has been examined precisely once. If you ever see an element leave the window without being tested, you advanced `mid` on the wrong branch.
- Why is it safe to advance mid after swapping with the low region?Because position `low` is the front of the already-classified middle region, so the element swapped back into `mid` has been examined before and is known to belong there. Nothing unexamined crosses the frontier, so `mid` can move on. When `low` and `mid` coincide, the swap is with the element itself and is trivially safe.
- What breaks if the loop condition is mid < high instead of mid <= high?The final unexamined record — the one at `mid == high` — is never classified. It stays in the gap between the second and third regions, so the output is correct only when that record happens to belong to the middle category. The failure looks input-dependent but is fully deterministic.
- How many comparisons per record does the three-way pass make, and what is its space cost?At most two: one to test the first category, and a second to distinguish the other two. That is still `O(n)` overall, and the extra space is `O(1)` because every record stays in the original storage and only moves by exchange. The pass makes at most `n` iterations, since the unexamined span shrinks by one each time.
saying these in an interview costs you the question
- Advances mid after every swap, on both branches
- Writes the loop as mid < high and drops the last element
- Believes the element coming from the high end is already classified
- Cannot say what the span between mid and high holds
- Claims the pass needs a second traversal to be correct