Two Sum with Hash Map
Implement or sketch code for Two Sum with Hash Map. Explain the logic, complexity, and pros/cons of this approach.
Answers use simple, clear English.
Audio N/AQuick interview answer
Logic: Find two indices whose values sum to target in one pass by storing value→index in a hash map and looking up complement = target − current on each step. Complexity notes included in code section when present.
Detailed answer
Logic: Find two indices whose values sum to target in one pass by storing value→index in a hash map and looking up complement = target − current on each step. Complexity notes included in code section when present. Pros: O(n) time, single pass, simple invariant to explain in interviews. Cons: O(n) extra memory; streaming with tiny RAM may force sort + two-pointer tradeoffs. Core: Find two indices whose values sum to target in one pass by storing value→index in a hash map and looking up complement = target − current on each step. Real-time example: Checkout promo: given item prices [12, 7, 3, 9] and gift-card balance 16, return indices of 7 and 9. Pros: O(n) time, single pass, simple invariant to explain in interviews. Cons: O(n) extra memory; streaming with tiny RAM may force sort + two-pointer tradeoffs. Common mistakes: Reusing the same index; storing before checking complement (allows self-pair). Best practices: Clarify uniqueness assumption; mention index vs value return requirement upfront. Audience level: Junior.
Full explanation
Find two indices whose values sum to target in one pass by storing value→index in a hash map and looking up complement = target − current on each step.
Real example & use case
Checkout promo: given item prices [12, 7, 3, 9] and gift-card balance 16, return indices of 7 and 9.
Pros & cons
Pros: O(n) time, single pass, simple invariant to explain in interviews. Cons: O(n) extra memory; streaming with tiny RAM may force sort + two-pointer tradeoffs.
Code example
def two_sum(nums: list[int], target: int) -> list[int]:
seen: dict[int, int] = {}
for i, x in enumerate(nums):
need = target - x
if need in seen:
return [seen[need], i]
seen[x] = i
raise ValueError("no pair")Practice code · python (view only · no execution)
def two_sum(nums: list[int], target: int) -> list[int]:
seen: dict[int, int] = {}
for i, x in enumerate(nums):
need = target - x
if need in seen:
return [seen[need], i]
seen[x] = i
raise ValueError("no pair")Common mistakes
Reusing the same index; storing before checking complement (allows self-pair).
Best practices
Clarify uniqueness assumption; mention index vs value return requirement upfront.
Follow-up questions
- How would you test Two Sum with Hash Map?
- What metrics prove Two Sum with Hash Map is healthy in prod?
- How does Two Sum with Hash Map change at 10× traffic?