# Two Sum ## # 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 hm, and the 2nd for loop checks if complement exists in for loop.

Note: need to check idx!=hm[complement] in 2nd for loop; o.w. fail on text case:

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


Complexity:

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

where $n$ is the length of nums.

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


### # One-pass HashMap

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

Note:

• the return order is reversed, as the complement is later seen than val
• idx!=hm[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]:
hm = {}
for idx,val in enumerate(nums):
complement = target-val
if complement in hm:
return [hm[complement], idx]
hm[val] = idx
return [-1, -1]


### # 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)
# two pointers
left, right = 0, len(nums)-1
while left<right:
sm = nums_sorted[left] + nums_sorted[right]
if sm < target:
left += 1
elif sm > target:
right -= 1
else:
return sorted([nums_sorted[left], nums_sorted[right]])
return [-1, -1]

Last Updated: 7/19/2020, 3:45:14 PM