LC001 - TwoSum

Problem

Given an array of numbers and a target integer, return two indices in the array where the values sum up to the target integer.

Assume that there is only one solution in the entire space of the array.

Example

Input: nums = [2,3,7,15], target = 9

Output: [0, 2]

Solution

Naive

The time complexity of the brute force solution is $\text{O}(N^2)$ since we have to go through (almost) the entire array for each index that we are checking.

However, the brute force solution does not require any additional memory than is already allocated for the initial array.

def TwoSum(nums: List[int], target: int) -> int:
	for i in range(len(nums)):
		diff = target-nums[i]
		for j in range(len(nums)-i-1):
				if diff == nums[i+j+1]:
				return [i, i+j+1]

Hash Map

The time complexity of the Hash Map solution is just $\text{O}(N)$ since we only have to go through the entire array once. This is because we save the index and value of the elements in a Python dictionary after we encounter them, so we only have to look up if the key exists and check its value (index) if it does.

However, this solution requires additional memory for the dictionary itself, which is $\text{O}(N)$ in size.

def TwoSum(nums: List[int], target: int) -> int:
	hashMap = dict()
	for i in range(len(nums)):
		diff = target-nums[i]
		if diff in hashMap:
			return [i, hashMap[diff]]
		else:
			hashMap[nums[i]] = i