Two pointers or hash map?
“A problem asks for pairs or triples meeting a condition. How do you choose between two pointers and a hash map?”
What this tests
- Whether the candidate knows two pointers needs sorted input and why.
- Awareness of the index-preservation problem introduced by sorting.
- Ability to reason about duplicates handling in each approach.
- Understanding of how each generalizes to 3-sum and beyond.
Strong answer
The decision is driven by three facts. Is the input sorted or may I sort it? Two Pointers (Opposite Ends) relies on order: if a[l] + a[r] is too small only l can move right, too large only r can move left. Without sortedness that discard rule is invalid. Do I need original indices? Sorting destroys them; a Hash Map of value → index preserves them for free. What are the space limits? Two pointers is O(1) extra; a hash map is O(n).
For 2-sum on unsorted input requiring indices, the hash map is the right answer in O(n). For 2-sum on sorted input or when only values matter, two pointers is cleaner and needs no memory. For 3-sum, sorting plus two pointers gives O(n^2) with trivial deduplication — skip equal neighbours — whereas the hash-map version is also O(n^2) but deduplication of triples becomes messy.
A strong candidate also mentions the hidden correctness argument for two pointers: it never skips a valid pair because every move discards only indices that provably cannot participate in a solution with the remaining range. And they note that the hash map approach cannot easily answer "count pairs with sum less than k", whereas two pointers answers it directly — the pattern is stronger for inequality conditions.
Green flags · Red flags
- Names sortedness as the precondition and explains the discard rule.
- Raises the index-preservation issue unprompted.
- Compares space:
O(1)vsO(n). - Handles duplicates in 3-sum by skipping equal neighbours and explains why that is complete.
- Notes that two pointers handles inequality targets (
< k) naturally.
- Applies two pointers to an unsorted array.
- Sorts and then returns sorted indices as if they were original.
- Proposes
O(n^3)for 3-sum with no improvement. - Cannot explain why two pointers does not miss pairs.
Follow-up questions
Each follow-up changes a requirement; the right answer changes with it.
a[i] + a[j] < k.