# Two Sum

ArrayHash TableTwo Pointers

## # Solution

Using hashmap takes $O(n)$ time whereas sorting takes $O(\log n)$ time.

### # Two-pass HashMap

The 1st for loop stores mappings from val to idx in HashMap hashmap, and the 2nd for loop checks if complement exists in for loop.

Note: need to check idx!=hashmap[complement] in 2nd for loop; otherwise fail on text case:

nums = [3,2,4]
target = 6

1
2

Complexity

time: $O(n)$
space: $O(n)$

where $n$ is the length of nums.

def twoSum(self, nums: List[int], target: int) -> List[int]:
hashmap = {}
# store val->idx in hashmap
for idx, val in enumerate(nums):
hashmap[val] = idx
# for each num, check if target-num exists in hashmap
for idx, val in enumerate(nums):
complement = target-val
if complement in hashmap and idx != hashmap[complement]:
return [idx, hashmap[complement]]
return [-1, -1]

1
2
3
4
5
6
7
8
9
10
11

### # One-pass HashMap

Compared w/ two-pass HashMap, this solution omits the 1st for loop to store all mappings on hashmap.

Note:

• the return order is reversed, as the complement is later seen than val
• idx!=hashmap[complement] condition to return is no longer needed because it's always true in a single for loop

Complexity

time: $O(n)$
space: $O(n)$

def twoSum(self, nums: List[int], target: int) -> List[int]:
hashmap = {}
for idx, val in enumerate(nums):
complement = target - val
if complement in hashmap:
return [hashmap[complement], idx]
hashmap[val] = idx
return [-1, -1]

1
2
3
4
5
6
7
8

### # Sort

Create nums_sorted to sort nums and store mappings from val to idx in List[(int, int)] format. Then use two pointers to search for matching indices.

Complexity

time: $O(n \log n)$
space: $O(n)$

def twoSum(self, nums: List[int], target: int) -> List[int]:
# store val->idx in List[(int, int)]
nums_sorted = []
for idx, val in enumerate(nums):
nums_sorted.append((val,idx))
# sort
nums_sorted.sort(key=lambda elt: elt[0])
# two pointers
left, right = 0, len(nums)-1
while left < right:
sm = nums_sorted[left][0] + nums_sorted[right][0]
if sm < target:
left += 1
elif sm > target:
right -= 1
else:
return sorted([nums_sorted[left][1], nums_sorted[right][1]])
return [-1, -1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18