ORIGINAL TECHNICAL PRACTICE
Choose the right hash-map invariant
Given a list of integers and a target, explain how to find two distinct positions whose values add to the target. What changes if you must return every pair?
Written for independent practice. The model answer presents one approach; clarify constraints and explain alternatives.
A REASONED APPROACH
Model answer.
A one-pass map can store each value’s earlier position. Before inserting the current item, look for its complement. This order prevents reusing the same position, while still supporting equal values at different positions.
Work through it
- State whether one answer or every answer is required, and define the no-match result. For [3,3] and target6, positions0 and1 are valid.
- At position i, the map contains only positions smaller than i. If target minus the current value exists, return those two positions.
- For every pair, store lists of earlier positions and emit each matching pair. Output size can itself be quadratic, so describe complexity in terms of both input and output.
Tradeoffs to discuss
- Expected time is O(n) and auxiliary space O(n) for one answer under ordinary hash-table behavior. Sorting offers a different time/space tradeoff but changes index handling.
Common pitfalls
- Inserting before checking can match an element with itself. Storing only one position loses results when all pairs are requested.