1. Which invariant fits a repeated “have I seen X?” question?
The source invariant says, “Hashing: trade O(n) space to make ‘have I seen X?’ an O(1) question.”
2. When scanning stock prices, which carried fact matters?
The source invariant says, “Best sell = today's price minus the cheapest price seen so far; one pass, carry the min.”
3. Maximum Subarray versus Product Except Self: which sentence resets the local candidate?
The Kadane source invariant says, “A running sum that has gone negative can never help a future subarray, so reset it: cur = max(x, cur+x).” The product source says, “answer[i] = product of everything to the left times product of everything to the right; two sweeps, no division.”
4. Which invariant fits Merge Sorted Array?
The merge source invariant says, “Fill from the end with two pointers walking inward, so you never overwrite a value you still need.” The same-direction source says, “A write pointer chases a read pointer; each moves forward only, so the whole pass is O(n).”
5. Which cancellation invariant fits Missing Number rather than Majority Element?
The XOR source invariant says, “x XOR x = 0, so XOR-ing 0..n against the array cancels every present number and leaves the missing one.” The Boyer-Moore source says, “A true majority survives pairwise cancellation; when the count hits zero, adopt a new candidate.”
6. Range Sum Query asks many sums on one fixed array. Which invariant applies?
The source invariant says, “Precompute a running total once, then answer any range or split in O(1).”
Self-check gate
Pass tonight if all three are true
One easy hashing problem and one prefix-sums problem pass from a blank file in under 15 minutes each.
Every revised problem either passes on run one or two, or gets a clear WA: <root cause> note.
Range Sum Query - Immutable has the extra leading 0 prefix cell and answers with subtraction.
If you miss the gate, do not tick Revision Done. Add the failed problem to the next revision list, compare only after the attempt, and write the invariant that would have prevented the miss.