Given an array of integers, return the indices of the two numbers that add up to a given target.
Input: nums = [5, 2, 3], target = 8 Output: [0, 2]
Input: nums = [3, 2, 4], target = 6 Output: [1, 2]
Input: nums = [5, 5], target = 10 Output: [0, 1]
Constraints
We need to find the combination of which two numbers add up to a given target. We can split this into two steps: 1.) Iterate over every possible pair of numbers 2.) Check if a given pair sums up to our target.
How do we iterate over every pair of numbers? We can start with the first number and compare it against every other number in the array. Then we move the next number and compare it against every other number and so on until we have found our solution.
We can then easily check if a given pair adds up to our target. If it does then we have found our solution and we can return the two indices.
From the diagram, we can see this approach in action. Where i
and j
represent the index pairs. On each iteration, we calculate the sum and see if it is equal to our target. Notice how j
is never behind i
, which ensures that we never re-evaluate already evaluated sums.
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
# 1. Iterate over every possible number pair
for i in range(len(nums)):
# j is always ahead of i so that we don't re-evaluate already evaluated sums
for j in range(i+1, len(nums)):
# 2. Check if a given pair adds up to our target
if nums[i] + nums[j] == target:
# Return the indices when a pair has been found
return i, j
1class Solution:
2 def twoSum(self, nums: List[int], target: int) -> List[int]:
3 # 1. Iterate over every possible number pair
4 for i in range(len(nums)):
5 # j is always ahead of i so that we don't re-evaluate already evaluated sums
6 for j in range(i+1, len(nums)):
7 # 2. Check if a given pair adds up to our target
8 if nums[i] + nums[j] == target:
9 # Return the indices when a pair has been found
10 return i, j
Time Complexity: O(n<sup>2</sup>)
, where n
is the size of the array. For each number, we have to evaluate every other number in the array.
Space Complexity: O(1)
, disregarding the input, all other variables have constant space.
We can build on the brute force solution and see that there is a lot of repeated work. This is because we iterate over the array multiple times.
Why do we need to iterate multiple times? For each number, we try to find another number which sums to the target. We refer to this other number as the "complement", and to find this number we check every other element in the array.
We can rephrase the previous algorithm: 1.) Iterate over every number in the array 2.) For each number scan the rest of the array to see if there is another number which sums to the target.
Notice how we repeatedly search the array for this "complement" number (step #2 above), which takes O(n)
time. Is there some way we can do this step faster?
We can reduce this repeated work by using a hash table. A hash table is a data structure which stores key-value pairs, a value can be looked up with a given key in constant time. We can store a number with its index in the hash table. Then when we need to check if the complement number is in the array, we can do so in constant time.
With this in mind we can break down our hash table algorithm into steps:
1.) Iterate over every number in the array This can be done with a simple for loop.
2.) Calculate the complement
The complement is the other number that would sum to the target and can be calculated as target - num
.
3.) Check if that complement is in our hash table If the complement is in the hash table then we can look up its index and we have our solution! If it is not then we continue to search the array.
4.) Add the current number to our hash table The current number may sum up with another number that we have not yet evaluated. We can store the number in the hash table as a key with the index as the value for future checks.
From the diagram, we can see how the hash table is modified and evaluated through each iteration until we find a sum.
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
# Our hash table that stores at which index the number is at
numToIndex = {}
# 1. Iterate over every number in the array
for i in range(len(nums)):
# 2. Calculate the complement that would sum to our target
complement = target - nums[i]
# 3. Check if that complement is in our hash table
if complement in numToIndex:
return numToIndex[complement], i
# 4. Add the current number to our hash table
numToIndex[nums[i]] = i
1class Solution:
2 def twoSum(self, nums: List[int], target: int) -> List[int]:
3 # Our hash table that stores at which index the number is at
4 numToIndex = {}
5
6 # 1. Iterate over every number in the array
7 for i in range(len(nums)):
8 # 2. Calculate the complement that would sum to our target
9 complement = target - nums[i]
10
11 # 3. Check if that complement is in our hash table
12 if complement in numToIndex:
13 return numToIndex[complement], i
14
15 # 4. Add the current number to our hash table
16 numToIndex[nums[i]] = i
O(n)
, where n
is the size of the array. We iterate over every number in the array and the hash table lookup/add operations take constant time.O(n)
, where n
is the size of the array. Our hash map stores every number in the input array.Given an array of integers, transform the array in-place to a max heap.
Given an array of integers, return an array of triplets such that i != j != k and nums[i] + nums[j] + nums[k] = 0.
Given the head of a linked list, reverse the list and return the new head.
interviewing.io is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.
Book mock interviews with engineers from Google, Facebook, Amazon, or other top companies. Get detailed feedback on exactly what you need to work on. Everything is fully anonymous.