Pattern Selection and Proof

The noun in the prompt is not the pattern

Consider this problem:

Given an integer array, count the non-empty contiguous subarrays whose sum is exactly k.

“Contiguous” makes a sliding window tempting. That choice is already in trouble. The array may contain negative values, so expanding the right edge can decrease the sum and removing the left edge can increase it. There is no one-way rule for restoring validity. Worse, the output is a count of all matching ranges, including overlapping ones. A single active window does not represent that result.

The difficulty is not recognizing a better label. It is finding a fact that makes every valid range visible. Let prefix[j] be the sum before position j. The range from i through j - 1 sums to k exactly when

prefix[j] - prefix[i] = k

or, equivalently, when an earlier prefix equals prefix[j] - k. Now the data structure follows from the operation: for each current prefix, look up how many times one exact earlier value has occurred.

seen = {0: 1}
prefix = 0
answer = 0

for x in nums:
  prefix += x
  answer += seen.get(prefix - k, 0)
  seen[prefix] += 1

The map stores counts rather than mere membership because equal prefix sums at different positions create different subarrays. The initial zero represents the empty prefix, which allows a matching range to begin at index zero.

The invariant is precise: before the current prefix is inserted, seen[s] is the number of earlier boundaries whose prefix sum is s, and answer counts all matching subarrays ending before the current boundary. The lookup adds exactly the valid starts for the current end. It invents none, because each reported start satisfies the equation; it misses none, because every valid range has one earlier boundary with the required prefix. Each boundary is processed once, giving expected O(n) time and O(n) space.

That argument answers four questions at once: why a map, why this algorithm is correct, what remains true during the scan, and why sliding window was rejected. Pattern selection is strongest when those answers come from the same observation.

Selection is a sequence of eliminations

The atlas offers many plausible tools. The fastest way through them is not to ask, “Which pattern does this resemble?” Ask what the solution must preserve and let the answers eliminate candidates.

Begin with the result. A value, count, path, order, decision, and enumeration are different artifacts even when they arise from the same input. “Can these courses be completed?” permits cycle detection. “Return a valid course order” requires retaining the order. “Return every valid order” changes the output size so radically that a polynomial-time search for one order no longer answers the question.

Then apply constraint pressure. Input size rules out entire complexity classes. The value domain may make an array or bitset possible; streaming may rule out sorting; point updates may invalidate static prefix sums. Constraints are not a final complexity recital. They determine what may be built.

Define state identity next. Two partial executions may share one state only if their legal futures are identical for this problem. A graph node alone is enough for ordinary reachability. It is not enough when reaching the same node with a different remaining fuel allowance changes the available paths. A DP memo key, a visited key, and a cache key all make this same promise.

Now name the operations the algorithm performs repeatedly. Exact lookup suggests hashing; next-by-priority suggests a heap; ordered predecessor or range queries require order-preserving structures; repeated neighbor expansion suggests a graph representation. This is the answer to “Why this data structure?” The structure earns its place by making the necessary operation cheap without erasing a fact the result still needs.

Only then choose the movement of the algorithm: advance two boundaries, explore a frontier, pop dominated candidates, combine smaller states, exchange a local choice into an optimum, or enumerate and restore choices. The name of the movement is useful shorthand. Its invariant is the reason it works.

Finally, reject the nearest rival. A counterexample is often the shortest route to clarity. Denominations [1, 3, 4] and amount 6 kill “take the largest coin first”: greedy returns three coins, while 3 + 3 uses two. Negative values kill a sum window whose boundaries rely on monotonicity. Weighted edges kill the claim that first discovery by ordinary BFS fixes the shortest distance. A rejection test does more than defend the chosen answer; it identifies the assumption carrying the proof.

Proof should explain the code you are about to write

A correctness argument need not sound ceremonial. For an iterative algorithm, it usually has three parts:

1. State what is true before an iteration or state transition.
2. Show that the next operation preserves that fact.
3. Connect termination to the requested result.

Suppose k sorted lists must be merged. Keep the smallest unseen element from each non-empty list in a min-heap. Initially the heap has one representative from every active list. Its root is therefore the smallest unseen element overall. Popping that root and pushing its successor restores one representative for the same list. When the heap empties, every item has been emitted once and in order. If there are N items in total, each is pushed and popped once, so the cost is O(N log k) time and O(k) auxiliary space.

The explanation and implementation have the same shape. If the code ever holds two candidates from one list but none from another, the proof tells you what broke. That diagnostic value is why the invariant belongs before or during implementation, not in a speech added after the tests pass.

Different families expose different kinds of safe progress:

• Two pointers and binary search discard a region only when ordering proves that no discarded candidate can improve or contain the answer.
• Sliding windows move forward when adding and removing elements changes validity predictably. Monotonic stacks and deques discard a candidate only after another candidate dominates it for every possible future use.
• BFS fixes shortest distance on first discovery only with equal-cost edges. Dijkstra’s algorithm needs non-negative weights and a priority frontier; stale heap entries must be rejected or prevented.
• Topological sort removes a zero-indegree vertex because it has no unmet prerequisite in the remaining graph. If vertices remain after no such choice exists, a directed cycle remains.
• Dynamic programming proves a state from already-correct predecessor states. Backtracking instead proves that its branches are complete and that state is restored before a sibling branch begins.
• Greedy algorithms require a safe-choice argument: an optimal solution can be exchanged to include the local choice, or the constructed solution stays ahead on the measure that determines the optimum.

These are not phrases to attach to a favorite pattern. They are obligations. If you cannot say which candidates a pointer move discards, which histories a memo key merges, or why a greedy exchange preserves feasibility, the next step is to repair the model rather than start coding.

One requested result can admit several patterns

“Return the k points closest to the origin” does not determine one best algorithm. The environment completes the question.

If all points fit in memory and simplicity matters, sort by squared distance and return the first k. The sorted prefix contains the k smallest keys in O(n log n) time. Squared distance preserves the required ordering without paying for square roots.

If points arrive as a stream or k is much smaller than n, keep a max-heap of at most k points. Its root is the worst member of the best set seen so far. A new point enters only if it improves that set. The invariant gives O(n log k) time and O(k) space, and it works without retaining the stream.

If the full array may be rearranged in place and expected linear time is worth the extra implementation risk, quickselect can partition by rank. It need not sort the chosen prefix internally because the prompt asks for a set, not ordered output. With an appropriate randomized pivot its expected cost is O(n), but the worst case is O(n²); pivot policy now belongs in the discussion.

None of these answers is senior merely because it is faster on paper. The senior move is to state the assumption that makes one of them preferable and to avoid promising an output property—such as sorted results—that the prompt did not request.

Some wording changes the kind of structure, not just its cost. “Use every airline ticket exactly once” is an edge-exhaustion problem; ordinary reachability DFS does not solve it and can mishandle duplicate tickets. A Hierholzer-style construction consumes each directed edge and appends an airport only after its outgoing edges are exhausted. Reversing that postorder produces the itinerary. The familiar word “graph” identified the domain, but “every edge exactly once” identified the governing invariant.

When one changed constraint breaks the proof

After finding a solution, change one promise and locate the first sentence of the proof that becomes false.

• Allow negative values in a sum problem, and a sliding window may lose the monotonic behavior that justified moving its boundaries.
• Add updates between range-sum queries, and static prefix checkpoints become stale. A Fenwick tree or segment tree may now match the operation profile.
• Give graph edges different non-negative weights, and first discovery by BFS no longer fixes shortest distance; a priority frontier becomes necessary.
• Require duplicate counts, and a set may erase multiplicity that a count map must retain.
• Let repeated visits improve a route, and a Boolean visited set may become a distance map or a key containing node plus resource state.
• Raise n from 20 to 200,000, and a correct 2^n subset algorithm becomes unusable. The problem now needs more structure, an approximation, or a revised requirement—not a micro-optimization.
• Require stable or lexical tie-breaking, and unordered traversal may need ordered adjacency, a stable sort, or an explicit secondary key.

This is a better follow-up habit than patching the existing code immediately. If the required operation changed, the broad algorithm may survive with a new data structure. If state identity or the safe-progress argument changed, the proof—and usually the algorithm—must be rebuilt.

Production scale makes hidden operations visible

An interview solution should not impersonate a production system, but it should survive an honest scale conversation. “O(n)” is incomplete when the input does not fit in memory, the map has unbounded cardinality, or each loop iteration copies a growing substring.

Ask where the data lives and how it arrives. The prefix-count algorithm from the opening can consume a stream, but exact counting may retain one entry for every distinct prefix sum. A bounded-memory requirement changes the problem; there is no general exact constant-space replacement. External state, an approximate answer, a bounded value domain, or a different query contract would need to be negotiated.

Ask whether the data changes between queries. Sorting and prefix arrays are powerful because they pay preprocessing cost for a stable collection. With frequent updates, that bargain may fail. The right comparison is the whole workload: build cost, query cost, update cost, memory, and concurrency—not the complexity of one method in isolation.

Ask what one “operation” hides. Hashing a long composite key, copying slices, leaving stale heap entries, expanding a dense implicit graph, and recursively materializing every construction can dominate the visible loop. If the output itself is exponential, no pattern can emit it in polynomial total time; the question becomes whether the caller needs all results, an iterator, a count, or one witness.

Finally, name the system boundary. A heap chosen for an in-memory top-k calculation does not decide partitioning across machines, merge semantics, late events, or failure recovery. The local invariant remains useful, but the distributed design needs additional invariants about ownership and replay. That is the right production answer: carry the proof as far as it reaches and say where a new proof is required.

Put the selection under pressure

Before coding a mixed problem, write six short lines:

result:
constraints and scale:
state and required operations:
selected pattern and invariant:
nearest rejected alternative:
correctness and cost:

Try the form on these prompts:

• longest substring without repeated characters;
• subarray sum equals k with negative values;
• largest rectangle in a histogram;
• word-ladder shortest transformation;
• partition equal subset sum;
• generate all valid parentheses;
• search a rotated sorted array;
• online top k events by score.

For each solution, mutate one condition: add negative values, require streaming, introduce updates, weight the edges, preserve duplicates, demand a stable tie-break, or increase n by two orders of magnitude. Do not ask only whether the old code still runs. Identify which invariant, operation cost, or state definition has stopped being true.

A defensible spoken explanation is compact:

“We need this result under these constraints. I am storing this state because it supports these repeated operations. This invariant makes the next step safe. I rejected the nearest alternative because this assumption fails. The algorithm is correct by this preservation argument and costs this much. If the constraint changes, this is the first choice I would reopen.”

That is the atlas compressed into a working habit. The goal is not to mention every candidate pattern. It is to make the chosen one inspectable—and to know exactly when its permission to discard work expires. The next kind of coding round enlarges the artifact from one algorithm to a small running system, but the discipline carries over unchanged: define the contract, protect the invariant, and make each added mechanism earn its place.

Related reading

• Chapter 31: Complexity and Constraint Analysis
• Chapter 39: Arrays and Strings
• Chapter 45: Graphs
• Chapter 47: Greedy Algorithms
• Chapter 48: Dynamic Programming
• Chapter 51: The Machine-Coding Round