Notes on how to solve the Two Sum problem
Table of Contents
This series of post is like my coding diary – a place where I jot down what worked (and what didn’t) so that future-me can have an easier go at it. In this post I’ll take a look at the first problem on LeetCode
Problem statement
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
Examples
Example 1:
Input: nums = [2,7,11,15], target = 9 → Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:
Input: nums = [3,2,4], target = 6 → Output: [1,2]
Example 3:
Input: nums = [3,3], target = 6 → Output: [0,1]
My thought process
The first thing that comes to mind is to cycle through the array and check every possible pair of numbers. This would be a O(n^2) solution, which is not ideal, but it’s a start.
The first example is one of the best cases for this approach because on the first iteration we would find the solution since 2 + 7 = 9. So for this, I’ll use the second example provided.
nums = [3, 2, 4]
target = 6
for i in range(len(nums))
for j in range(i + 1, len(nums))
i = 0
j = 0
↓
[3, 2, 4] → 3 + 2 is equal 6? → FALSE
↑
j = 1
↓
[3, 2, 4] → 3 + 4 is equal 6 → FALSE
↑
i = 1
j = 0
↓
[3, 2, 4] → 2 + 4 is equal 6? → TRUE
↑
So, in this case, we would return [1, 2].
This is a good start, but it’s not enough. We need to find a way to check if the sum of two numbers is equal to the target. For this, I’ll use the first example.
It would be great if we could do this by scanning the array just one time. To do this, we need a data structure that allows us to check if a number is already in the array. An hashmap would be perfect for this.
nums = [3, 2, 4]
target = 6
seen = {}
for i in range(len(nums))
i = 0
↓
[3, 2, 4]
What is the number that added to 3 gives 6? 3 + x = 6 → x = 3
Have we already seen 3?
No, so we add 3 and its index to the hashmap: seen = {3: 0}
i = 1
↓
[3, 2, 4]
What is the number that added to 2 gives 6? 2 + x = 6 → x = 4
Have we already seen 4?
No, so we add 4 and its index to the hashmap: seen = {3: 0, 4: 1}
i = 2
↓
[3, 2, 4]
What is the number that added to 4 gives 6? 4 + x = 6 → x = 2
Have we already seen 2?
Yes, so we return the index of 2 and the current index: [1, 2]
This is a good solution, but we are making a tradeoff here. We are using more memory to reduce the time complexity of our algorithm. But it is a good tradeoff because we are reducing the time complexity from O(n^2) to O(n).
My solution
# Using a hashmap
def twoSum(self, nums: List[int], target: int) -> List[int]:
seen = {}
for i in range(len(nums)):
complement = target - nums[i]
if complement in seen:
return [seen[complement], i]
seen[nums[i]] = i
return []
Possible follow-up questions
What if the array is sorted and we can’t use extra memory?
We could use a two pointer approach. One pointer would start at the beginning of the array and the other at the end. If the sum of the two numbers is greater than the target, we move the right pointer to the left. If the sum is less than the target, we move the left pointer to the right. If the sum is equal to the target, we return the indices of the two numbers.
nums = [2, 7, 11, 15]
target = 9
i = 0
[2, 7, 11, 15]
↑ ↑
2 + 15 = 17 > 9 → move right pointer to the left
i = 1
[2, 7, 11, 15]
↑ ↑
2 + 11 = 13 > 9 → move right pointer to the left
i = 2
[2, 7, 11, 15]
↑ ↑
2 + 7 = 9 → return [0, 1]
This algorithm has a time complexity of O(n) and a space complexity of O(1). But it only works if the array is sorted. If it’s not, we would have to sort it first, which would take O(n log n) time. So the overall time complexity would be O(n log n).
class Solution:
# Two pointer approach, assumes nums is sorted
def twoSum(self, nums: List[int], target: int) -> List[int]:
left = 0
right = len(nums) - 1
while left < right:
current_sum = nums[left] + nums[right]
if current_sum == target:
return [left, right]
elif current_sum > target:
right -= 1
else:
left += 1
return []
What if duplicates exist in the array?
The hashmap approach and the two pointers approach here would still work. Say we have the following array:
nums = [1, 1, 1, 1]
target = 2
seen = {}
for i in range(len(nums))
i = 0
↓
[1, 1, 1, 1]
What is the number that added to 1 gives 2? 1 + x = 2 → x = 1
Have we already seen 1?
No, so we add 1 and its index to the hashmap: seen = {1: 0}
i = 1
↓
[1, 1, 1, 1]
What is the number that added to 1 gives 2? 1 + x = 2 → x = 1
Have we already seen 1?
Yes, so we return the index of 1 and the current index: [0, 1]
What if you could use the same element twice?
In this case we would need to add a check to see if the current number is equal to the complement. If it is, we would need to check if we have already seen the current number. If we have, we return the indices of the current number and the complement. If we haven’t, we add the current number to the hashmap if we are using the hashmap approach, or we move the left pointer to the right if we are using the two pointers approach.