1. Two Sum (LeetCode)
Model answer
The task
Given a list of integers and a target, return the indices of two distinct elements whose values add up to the target. The usual version guarantees a valid pair.
Key idea
As we scan the list, store each value’s index in a hash table. For the current value, check whether its needed complement has already appeared; this finds a pair in one pass.
Approach
- Create a dictionary mapping previously seen values to their indices.
- For each element, compute the complement needed to reach the target.
- If that complement is in the dictionary, return its stored index and the current index.
- Otherwise, store the current value and index, then continue.
from typing import List
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
# Map each value already visited to its index.
seen = {}
for index, value in enumerate(nums):
complement = target - value
# A match must come from an earlier, distinct element.
if complement in seen:
return [seen[complement], index]
seen[value] = index
# The standard problem guarantees a solution.
raise ValueError("No two elements sum to the target")
Complexity:
- Time: O(n), where n is the number of elements; each lookup and insertion is O(1) on average.
- Space: O(n), for the dictionary of values seen so far.
Common follow-ups
- What if there may be multiple valid pairs? Return the first pair found, or keep searching and collect pairs according to the required output rules.
- What if the input is sorted? Use two pointers from opposite ends for O(1) extra space; preserve original indices if those are required.
- What if values repeat? The dictionary stores indices, and checking before insertion ensures the current element is not paired with itself.