Write it yourself before they ask
Reading Two Sum is easy. Writing it while an interviewer watches is what gets you hired. Solve it yourself in the 14-day free trial, and the learning engine brings it back before you forget it.
The problem
Given an integer array arr and an integer target, return the indices of
the two numbers that add up to target, smaller index first.
You can't use the same element twice. If no pair adds up to target,
return an empty array.
Constraints
- 0 <=
arr.length<= 10^4:arrmay be empty or contain a single number. - -10^9 <=
arr[i]<= 10^9 and -10^9 <=target<= 10^9; values may repeat. - At most one pair adds up to
target.
Example
- Input
arr = [3, 8, 11, 5, 2, 7], target = 9- Output
[4, 5]
2 is at index 4 and 7 is at index 5, and 2 + 7 = 9.
How to solve it
The obvious answer is to try every pair. It never misses one, and on 10,000 numbers it's about 50 million sums. Say it out loud with its cost, O(n²), and move on.
When you reach a number n, its partner has to be target - n, its complement. So walk the array once and keep a hash map from the complement each earlier number needs to that number's index. If the current number is already a key, an earlier number was waiting for it: return that index and this one. Otherwise, store target - n with the current index and keep going.
Two Sum([-1,-2,-3,-4,-5], -8)
The run starts on [-1,-2,-3,-4,-5], -8.
Each number is checked against the map before its own complement goes in. That is why, with a target of -8, a single -4 can't pair with itself. If no number ever finds itself in the map, the loop ends and you return an empty list.
Expect the follow-up: what if the array is sorted? Put one pointer at each end. If the sum is too big, move the right pointer in; if it's too small, move the left one up. That's O(n) time with O(1) extra space. On an unsorted array, sorting first costs O(n log n) and scrambles the indices you have to return, so the hash map stays the answer.
Python solution
from typing import List
class Solution:
def two_sum(self, arr: List[int], target: int) -> List[int]:
num_dict = {}
for i, n in enumerate(arr):
if n in num_dict:
return [num_dict[n], i]
else:
num_dict[target - n] = i
return []Time and space complexity
- Time O(n)
- One pass, with one hash map lookup and at most one insert per number.
- Space O(n)
- In the worst case the map holds an entry for every number.