skip to content

In a three-way partition into below, equal and above a threshold, why does the scan index not advance after the high-side swap?

level: middleimportance: should knowfreq 52%

answer

  1. count regions, not indices
  2. one region is still unknown
  3. where does each swap pull from
  4. the high side is unexamined territory
  5. an unclassified value lands under the scan

basics

~20 s

The high-side swap pulls a value out of the still-unexamined region and drops it under the scan index. That value has not been classified yet, so the scan index must stay and inspect it next iteration.

solid answer

~40 s

Track four regions, not three: everything below the threshold, everything equal to it, the unknown middle, and everything above. The low-side swap exchanges the scanned value with a slot inside the already-classified equal region — so whatever lands under the scan index is known, and the scan index may advance. The high-side swap exchanges with a slot at the far edge of the *unknown* region, so an unclassified value lands under the scan index and must be examined next iteration; the high boundary shrinks instead. Advancing both symmetrically is the classic bug: one element is skipped, ends up in the wrong region, and the arrangement is silently wrong on inputs that contain above-threshold values. The loop runs while scan <= high, one pass, `O(1)` extra space.

code

pseudocode · 14 lines
pseudocode
low = 0
scan = 0
high = length(a) - 1
while scan <= high
    if a[scan] < t
        swap(a[low], a[scan])
        low = low + 1
        scan = scan + 1
    else if a[scan] == t
        scan = scan + 1
    else
        swap(a[scan], a[high])
        high = high - 1        // scan deliberately does not move
// [0,low) below   [low,scan) equal   [scan,high] unknown   (high,end] above

go deeper

for a junior

Recall that a three-way partition sorts values into below, equal and above a threshold in a single pass, without fully sorting the array, and needs no second buffer.

for a middle

Name the four regions and explain why the branch swapping toward the high side leaves the scan index in place while the low-side branch advances it, then justify the loop bound.

for a senior

Show you can review such a loop from its invariant: check the bound, check that the unknown region strictly shrinks in every branch, and check that no element escapes classification.

for a principal

Weigh the single-pass in-place arrangement against a plainer count-then-place version the team can maintain, and be explicit about which constraint — memory, one pass over slow input, or reviewability — decides it.

## Four regions, three indices A three-way partition rearranges an array so that all values below a threshold come first, all values equal to it next, and all values above it last — without fully sorting anything. Think of a window of sensor readings being triaged against an alarm level: under-alarm, at-alarm, over-alarm, in one pass, in the same buffer. The confusion that makes this loop feel tricky is counting three regions because there are three indices. There are **four**: | Region | Meaning | |---|---| | `[0, low)` | classified: strictly below the threshold | | `[low, scan)` | classified: equal to the threshold | | `[scan, high]` | **unknown** — not yet examined | | `(high, n-1]` | classified: strictly above the threshold | The unknown region sits between `scan` and `high` and shrinks from both ends. The loop runs exactly while that region is non-empty, i.e. while `scan <= high`. ## What each branch does to the unknown region **Value below the threshold.** Swap it with `a[low]`, then advance both `low` and `scan`. What comes back into `a[scan]` from `a[low]`? Either an element of the equal region — already classified — or, when `low == scan`, the same element you were just looking at. Either way the value now under the scan index is known, so the scan index may safely move on. The below region grew by one and the unknown region shrank by one from the left. **Value equal to the threshold.** It already belongs at the left edge of the unknown region, which is exactly where the equal region ends. Advance `scan` only. The equal region grew by one. **Value above the threshold.** Swap it with `a[high]` and decrement `high`. Now `a[high+1]` is correctly in the above region — but the value that came back into `a[scan]` was pulled from the *unknown* region, and nobody has looked at it. It could be anything. So `scan` must stay put and classify it on the next iteration. The unknown region shrank by one from the right. The asymmetry is not a quirk to memorise. It falls straight out of the region table: the low side hands you a classified value, the high side hands you an unclassified one. ## The bug this question aims at Writing `scan = scan + 1` in the high branch too — from an instinct that swaps should be symmetric — produces a loop that terminates, produces no error, and returns a wrong arrangement whenever the input contains above-threshold values. The skipped element lands wherever it happened to be swapped and is never compared to the threshold. It is a silent-wrong-answer bug, the kind that survives a small hand-traced example (try one with a single above-threshold reading and you may still get lucky) and fails on real data. The partner bug is the loop bound. `while scan < high` leaves the last slot of the unknown region unclassified, because at `scan == high` there is still exactly one element nobody has looked at. The bound must be `scan <= high`. ## Termination and cost Every iteration shrinks the unknown region `[scan, high]` by at least one — the scan index rises in two branches, the high index falls in the third. So the loop is guaranteed to end, in at most `n` iterations. Each element is compared to the threshold at least once and, in the high branch, possibly a second time after being moved; the total is `O(n)` comparisons with a small constant. Extra space is `O(1)` — the three indices and a temporary for the swap. Single pass over the data, which matters when the data is large or streamed off slow storage. ## The two-pass alternative, and when it is the better call You can also count how many values fall below, equal and above in one pass, compute the three region offsets, and place elements in a second pass. It is easier to explain and easier to review, but it either reads the data twice or needs somewhere to place elements while sources are still being read. Where the array must not be duplicated and the pass is hot, the single-pass version wins; where the code will be maintained by people who do not carry the four-region picture in their heads, the reviewable version can be worth its second pass. Whichever you pick, write the region invariant as a comment — that comment is the only thing that makes the loop checkable without simulating it. ## What the arrangement does not give you It does not preserve the relative order of the elements within each region: swaps move values across arbitrary distances. If the readings must stay in the order they arrived, this arrangement is the wrong tool, and you need one that only moves survivors leftward or one that builds output elsewhere.

  • Why must the loop condition be scan <= high rather than scan < high?
    Because the unknown region is the closed interval from scan to high. When they are equal, exactly one element is still unclassified. Stopping at `scan < high` leaves that element wherever it happens to sit, which is wrong unless it coincidentally belongs there. The loop is safe to end only once scan has passed high, i.e. once the unknown region is empty.
  • Why is the loop guaranteed to terminate?
    Every branch shrinks the unknown interval by exactly one: the below and equal branches raise the scan index, the above branch lowers the high index. A non-negative quantity that strictly decreases each iteration hits zero, so the loop ends within n iterations. That measure is also what you cite in review instead of hand-simulating the loop.
  • Does a three-way partition keep readings in their arrival order within each region?
    No. Swaps move values across arbitrary distances, so two below-threshold readings can come out reversed relative to how they arrived. If arrival order matters inside a region, the in-place partition is the wrong tool: you need an order-preserving sweep, or you build the three groups somewhere else and pay the extra space.

saying these in an interview costs you the question

  • Advances the scan index after every swap
  • Says the unknown region lies between low and scan
  • Claims the loop may stop at scan < high
  • Counts three regions because there are three indices
  • Expects arrival order preserved inside each region

context

resolving links…