1. Two Sum
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
Solution 1: Brute Force (Slow)
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i, n1 in enumerate(nums):
for j, n2 in enumerate(nums[i+1:], i + 1):
if n1 + n2 == target:
return [i, j]
return [-1, -1]
This is the most naïve solution that I could think of. We iterate over every number in the given list, and for each number, we combine it with every other value in the list to see if we have a match.
This solution is both functional and simple to understand, but it isn’t efficient enough for our purposes. It works in order O(n * n) time, when there is an O(n) solution out there.
Notes
The return statement at the end, return(-1, -1), is just there as a placeholder, as the problem tells us that we will always have a solution.
Also, this monstrosity (enumerate(nums[i+1:], i + 1)) simply calls the enumerate method with the portion of the list that is after index i (nums[i+1:]) and tells it to start counting at an index i + 1.
Solution 2: One pass, Linear
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
seen = {}
for i, n in enumerate(nums):
diff = target - n
if (diff) in seen:
return [i, seen[diff]]
seen[n] = i
return [-1, -1]
This solution is roughly the same amount of code, but much more efficient. This solution works by keeping track of the values that we have already seen, as well as their indices. The seen variable maps each value to its index in the list.
To begin, we loop through the list like normal. For each value, we calculate the complementary value that is would need to reach the target. For example, if the target value is 9, and the current n value is 5, then the compliment of n is target - n = 4.
Once we have calculated this complimentary value, we check to see if we have already seen it in the list. If we have, then we return the index associated it with our current index. If not, then we add the current value to the list and continue with our iteration.