skip to content

A scan that stops at the first duplicate it finds - what does that early exit actually save?

level: middleimportance: must knowfreq 58%

answer

  1. one witness settles the question
  2. cost follows the hit position
  3. the clean input still costs everything
  4. expected work drops, the guarantee does not
  5. counting cannot stop, existence can

basics

~20 s

Early exit saves everything after the answer: the elements never read and the per-element work never done. It cuts the expected cost, often enormously, but leaves the worst case untouched - an input with no duplicate is still read to the end.

solid answer

~40 s

The scan answers an **existence** question, so one hit settles it. Let `k` be the position of the first repeat and `n` the input size: the scan does work proportional to `k`, not to `n`, and everything past `k` - reading the element, testing it, anything downstream of the test - never happens. That is a real win on typical data, where duplicates show up early. It is not an asymptotic win: when no duplicate exists there is no early hit, `k` is `n`, and the scan reads everything. It also does not reduce the memory the scan already committed to for remembering what it has seen. Change the question to 'report every duplicate' and the early exit disappears, because no prefix can settle that answer.

code

pseudocode · 7 lines
pseudocode
function hasDuplicate(values)
    seen = emptySet()
    for each v in values
        if contains(seen, v)
            return true      // stops here; nothing after v is read
        add(seen, v)
    return false             // only this path reaches the end of values

go deeper

for a junior

Know that a scan answering 'is there one?' returns as soon as it finds one and does not look at the rest of the input, and that the answer is the same as an exhaustive scan would give.

for a middle

Express the cost in terms of the hit position rather than the input size, and say clearly that an input with no hit still costs a full pass - the worst case is unchanged.

for a senior

Judge whether the early exit is a real win for this data: how often a hit occurs early, whether the worst case is the normal case here, and what happens when the producer has no end.

for a principal

Notice when the requirement itself is the cost driver - asking for every duplicate instead of whether one exists forfeits early exit permanently - and push the question back before anyone optimises the loop.

## Two different questions about the same data 'Does this input contain a duplicate?' and 'which values are duplicated?' look like one task, but only the first can stop early. An **existence question** is settled by a single witness: once one repeated value is found, no remaining element can change the answer from yes. An **aggregation question** is settled only by the last element, because any element still to come could contribute. That distinction, not cleverness in the loop, is what makes early exit available. ## What the early exit actually removes Let `n` be the number of elements in the input and `k` the position at which the first repeat is found. - The `n - k` elements after the hit are **never read** from the source. - The per-element work for those elements - the membership test, the bookkeeping, anything that would have run per element - never happens. - If the scan sits at the end of a chain of steps, the earlier steps are never asked to produce those elements either, so their work disappears too. - The **time to an answer** drops from a function of `n` to a function of `k`. ## What it does not change 1. **The worst case.** On input with no duplicate at all there is no witness, so the scan must examine every element before it can answer no. The worst case stays proportional to `n`. Early exit improves the *expected* cost on realistic data; it does not improve the guarantee. 2. **The memory already committed.** A scan that remembers which values it has seen still grows that record for every element it read. Stopping at `k` bounds it at `k` entries rather than `n`, but the structure and its cost per element are unchanged. 3. **The answer.** Early exit is an evaluation decision, not a semantic one. A correct early-exit scan returns exactly what the exhaustive one would. ## Cost by input shape | Input | Position of first repeat | Elements read | Comment | |---|---|---|---| | Duplicate near the front | small `k` | `k` | the case that motivates early exit | | Duplicate near the end | `k` close to `n` | `k` | almost no saving | | No duplicate at all | none | `n` | worst case, unchanged by early exit | | Unbounded producer | small `k` | `k` | early exit is what makes the scan terminate at all | The last row is worth stating: over a producer with no end, an existence scan terminates exactly when a witness exists, and an exhaustive one never terminates. Early exit is not an optimisation there - it is the difference between an answer and no answer. ## Which terminal steps can stop, and which cannot A useful way to reason about a whole family of operations at once is to ask: *can any single element settle this?* - **Can stop early:** 'is there any element with this property', 'give me the first element with this property', 'do all elements have this property' (the first counterexample settles it), 'does this value occur'. - **Cannot stop early:** counting matches, summing, finding the maximum, sorting, grouping, or anything that must see every element because the last one can still change the result. This is why 'do we have duplicates?' and 'how many duplicates do we have?' have genuinely different costs. A team that asks the second question when it only needed the first has paid for a full pass it did not need - and the fix is a product decision about the question, not a faster loop. ## How to reason about it under pressure 1. Name the question: existence, first match, universal, or aggregate. 2. If it is one of the first three, name the witness that settles it. 3. State the cost as a function of the witness position `k`, and then state what `k` is in the worst case. 4. Say explicitly whether the data makes the worst case rare or normal - that is the difference between a real win and a hoped-for one. The last step is where interview answers separate. A candidate who says 'it stops early so it's fast' has not looked at the data; a candidate who says 'on our input duplicates cluster in the first few percent, so `k` is tiny in practice, but a clean file still costs a full pass' has.

  • A check that every element satisfies a predicate is run over an empty input. What does it return, and why?
    True. The check is settled by a counterexample, and an empty input contains none, so the scan stops immediately with nothing examined. The mirror check - 'does any element satisfy it' - returns false on the same input for the same reason: no witness. Candidates who reason from 'nothing to check, so it cannot answer' get both backwards.
  • The requirement changes from 'is there a duplicate' to 'list every duplicate'. What happens to the cost?
    The early exit disappears. No prefix can settle a listing, so every element must be read and the cost becomes proportional to `n` on every input, not just the worst one. The per-element bookkeeping also has to grow to record counts or occurrences rather than mere membership.

saying these in an interview costs you the question

  • Claims early exit improves the worst-case cost of the scan.
  • Thinks a count of matches can stop at the first match.
  • Says the scan reads half the input on average, whatever the data.
  • Believes stopping early can change the answer the scan returns.
  • Assumes memory falls as much as time does when the scan stops early.