Two Sum
Given an array, find two numbers that add up to a target number and return their indices.
Analysis
This problem can be solved by trying to add every number within the array. This approach is naive and has quadratic time complexity. It would look like
class SolutionTrivial:
def twoSum(self, nums: list[int], target: int) -> list[int]:
= len(nums)
n for k in range(n):
for j in range(k + 1, n):
if nums[k] + nums[j] == target:
return [k, j]
return [k, j]
There is a memoization that can be done to make this much faster, however it does have a large memory drawback. If we have a hash table where, target - num
, the difference required to complete the current number, num
, is stored with the index as its value, we can look for the difference in this hash table for a very low time cost. For instance, the following steps would do so:
nums: [1,2,3,4]
target: 5
iterations:
- k: 0
num: 1
diff: 4 # 5 - 1
num_in_map: false
map:
4: 0
# diff: index
- k: 1
num: 2
diff: 3 # 5 - 2
num_in_map: false
map:
4: 0
3: 1
- k: 2
num: 3
diff: 2 # 5 - 3
num_in_map: true
map:
4: 0
3: 1
2: 2
Better yet, this has at worst linear time complexity. An implementation of this is the following:
class SolutionTrivial:
def twoSum(self, nums: list[int], target: int) -> list[int]:
= len(nums)
n for k in range(n):
for j in range(k + 1, n):
if nums[k] + nums[j] == target:
return [k, j]
return [k, j]