Why does a one-pass seen-set beat sorting for finding the first repeated check-in badge?

## The requirement is about order A conference check-in desk records badge identifiers in the order they are scanned. Staff want the first badge that was scanned twice — the earliest point at which someone re-entered or a badge was cloned. Notice that this requirement mentions *arrival order*: the answer is defined by the position of the second scan in the log. ## Why sorting answers a different question Sorting the log puts equal identifiers next to each other, and a linear neighbour comparison then finds duplicates reliably. Equal keys really do become adjacent, so the "sorting can miss non-adjacent duplicates" worry is unfounded. The problem is subtler and worse: sorting **discards the ordering the requirement is stated in**. After sorting, the first duplicate you meet is the smallest duplicated identifier, which has nothing to do with which badge was re-scanned first. To keep the answer you would have to sort pairs of (identifier, original position) and then take the minimum second-occurrence position across all duplicate groups — more work and more code for a worse result. The cost profile is worse too. A comparison sort is Omega(n log n) — that lower bound is about comparison sorts specifically, and non-comparison sorts such as counting or radix escape it only when the key domain permits, which arbitrary badge identifiers may not. Sorting also has no early exit: it must order the whole log even if the repeat happens on the second scan. And it either mutates the caller's log or costs an O(n) copy. ## What the seen-set does instead One pass, one invariant: **the set contains exactly the badges from entries strictly before the current one.** For each entry, test membership first; a hit means this badge already appeared earlier in scan order, and because we are walking forward, this is the earliest second-scan we could have reached, so return immediately. Otherwise add the badge and continue. Expected O(1) per entry gives O(n) expected time overall, with worst-case O(n) per lookup if hashing degrades badly. Extra space is O(n) — the set may end up holding every distinct badge — and that memory is the price paid for the speed. Order inside the loop is again the whole correctness argument. Insert before testing and every badge is instantly "already present", so the first entry is reported as a duplicate. Test-then-insert is what makes the invariant true. ## The edge inputs an interviewer probes - **Empty log.** The loop body never executes; the function returns "no repeat". Candidates who claim it returns the first badge have not traced the loop. - **Every badge distinct.** n membership tests all miss, n insertions happen, and the function returns "no repeat" after touching the whole log. This is the worst case for both time and memory. - **Every badge identical.** The first entry misses and is inserted; the second entry hits and returns. One insert, two iterations — the best case, and a good demonstration of the early exit sorting cannot offer. - **A single entry.** One miss, one insert, no repeat. ## Set or map here? A set is correct precisely because the requested output is the badge itself, which you already hold in hand when the hit occurs. Change the requirement to "report the position of both scans" and it becomes a map from badge to its first position, because the earlier position is now data that must travel with the key. Change it to "how many times was each badge scanned?" and it becomes a map to a count, and the early exit disappears — you now have to read the whole log. Let the required output pick the structure, and notice that each of those three requirements has a different best structure even though all three are "about duplicates". ## A related mis-statement worth avoiding After a full pass, the set's size is the number of **distinct** badges, not the number of duplicates. The count of duplicate scans is the log length minus that size, and even that tells you nothing about which badge repeated first. Reporting the set's size as a duplicate count is a common slip. ## What to say when asked Lead with the observation that the question is stated in arrival order, so any approach that reorders the log answers a different question. Then give the loop and its invariant, the O(n) expected time versus O(n log n), the early exit, the O(n) memory you traded for it, and the empty and all-identical edge cases.