How to Solve Three Sum
Three Sum Introduction
Three Sum Introduction
The Three Sum problem involves finding all unique triplets of numbers in an array that sum up to a given target. As an extension of the classic Two Sum problem, it can be solved efficiently by building on top of that problem and applying a variety of sorting and hashing approaches.
Three Sum Problem
Three Sum Problem
Given an array of integers, return an array of triplets (in any order) such that i != j != k and nums[i] + nums[j] + nums[k] = 0. Note that the solution set must not include duplicate triplets (i.e., [1, 0, 0] and [0, 1, 0] are duplicative).
Example Inputs and Outputs
Example 1
Input: [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]]
Example 2
Input: [1,2,7,12] Output: []
Example 3
Input: [7,4,-7,0] Output: [[0,-7,7]], OR [[7,-7,0]], etc.
Practice the Three Sum Problem With Our AI Interviewer
Practice the Three Sum Problem With Our AI Interviewer
Three Sum Solutions
Three Sum Solutions
This problem is a continuation of a similar problem aptly-named "Two Sum" in which the premise is very similar. As with that problem, for Three Sum there are naive, combination-driven approaches as well as more-efficient approaches.
1. Brute Force
When approaching an algorithms problem, particularly when thinking about the brute force approach, it is often easiest to start by thinking about how you would solve a given problem if you were to solve it by hand. Take Example 3, [7, 4, -7, 0]. While the answer for this example input may be obvious by simply looking at the array and thinking about the problem, you could also solve it by generating all the possible triplet combinations and evaluating which triplets meet the required criteria A + B + C = 0.
Input: [7,4,-7,0] Triplets: [[7, 4, -7], [7, 4, 0], [7, -7, 0], [4, -7, 0]]
Now the task becomes how we can generate the above list of triplets using code. For brute-force combinations problems the answer is often nested for loops, and given we are generating a list of triplets (vs. pairs or quadruplets) we can utilize three nested for loops to generate our list of triplets. From there we can scan the list and check whether each triplet meets our requirement of summing to zero.
The "no duplicates" requirement adds a bit of complexity. If we were to utilize three for loops, there would be no way to eliminate duplicates and thus it would be impossible to find a valid solution; however, we can tackle this by sorting the triplet before saving it to a hash map using a stringified-triplet as the key.
Three Sum Python and JavaScript Solutions - Brute Force
def threeSum(nums: List[int]) -> List[List[int]]:
three_sums = {}
for i in range(0, len(nums)):
for j in range(i+1, len(nums)):
for k in range(j+1, len(nums)):
if nums[i] + nums[j] + nums[k] == 0:
sorted_answer = sorted([nums[i], nums[j], nums[k]])
three_sums[str(sorted_answer)] = [nums[i], nums[j], nums[k]]
return three_sums.values()1def threeSum(nums: List[int]) -> List[List[int]]:
2 three_sums = {}
3 for i in range(0, len(nums)):
4 for j in range(i+1, len(nums)):
5 for k in range(j+1, len(nums)):
6 if nums[i] + nums[j] + nums[k] == 0:
7 sorted_answer = sorted([nums[i], nums[j], nums[k]])
8 three_sums[str(sorted_answer)] = [nums[i], nums[j], nums[k]]
9 return three_sums.values()Time/Space Complexity
- Time Complexity:
O(n³) - Space Complexity:
O(len(answer))(space complexity will scale in line with the number of triplets found)
2. Two Sum Hashmap
Now that we've solved the problem using a brute-force, combinations driven approach let's think about how we can leverage common data structures to find a more efficient solution.
Thinking back to the Two Sum problem described earlier, consider the following nums array and target value: nums = [1, 7, 12, 4], target= 19.
If we are iterating over this list ([1, 7, 12, 4]) and on the 0th index, our current value is 1. Therefore, in order to sum to our target of 19, we are looking for 18. From an algebra perspective we know this because if X + 1 = 19, so X = 19 - 1.
From here, the naive approach would be to scan the list looking for 18, however we can leverage a data structure that allows for constant time lookups (namely, a set or hashmap) in order to avoid repeatedly scanning the list. To translate the above logic to code, our Two Sum algorithm (which is relevant to Three Sum, I promise) looks like this:
# Prompt: Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
def twoSum(self, nums: List[int], target: int) -> List[int]:
nums_dict = {val: idx for idx, val in enumerate(nums)}
for idx, val in enumerate(nums):
looking_for = target - val
if looking_for in nums_dict and nums_dict[looking_for] != idx:
return [idx, nums_dict[looking_for]]1# Prompt: Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
2def twoSum(self, nums: List[int], target: int) -> List[int]:
3 nums_dict = {val: idx for idx, val in enumerate(nums)}
4 for idx, val in enumerate(nums):
5 looking_for = target - val
6 if looking_for in nums_dict and nums_dict[looking_for] != idx:
7 return [idx, nums_dict[looking_for]]With that idea in mind, we can turn our attention back to Three Sum and consider how we can use a similar approach to solve the problem at hand. In this case, we can generate a hashmap that contains all two-item combinations in the array keyed by the sum of those two items, then use that hashmap to determine which tuples can be combined with any item in the array to sum to 0 (roughly, sum(Tuple[X, Y]) + otherIntegerZ == 0).
Three Sum Python and JavaScript Solutions - Two Sum Hashmap
from collections import defaultdict, Counter
def twoSumsMap(nums: List[int]) -> Dict[int, Tuple[int, int]]:
two_sums_map = defaultdict(set)
for i, val_one in enumerate(nums):
for j, val_two in enumerate(nums[i+1:]):
two_sums_map[val_one + val_two].add(
(val_one, val_two)
if val_one <= val_two else
(val_two, val_one)
)
return two_sums_map
def threeSum(nums: List[int]) -> List[List[int]]:
# O(n^2)
two_sums_map = self.twoSumsMap(nums)
# O(n)
counter_for_nums = Counter(nums)
three_sums = {}
# iterating on the dictionary instead of `nums` in order to avoid duplicative work
for curr_val in counter_for_nums.keys():
two_sum_tuples_for_val = two_sums_map[-curr_val]
for val_one, val_two in two_sum_tuples_for_val:
if (curr_val != val_one and curr_val != val_two) or counter_for_nums[curr_val] >= 3:
sorted_vals = sorted([curr_val, val_one, val_two])
three_sums[str(sorted_vals)] = sorted_vals
return three_sums.values()1from collections import defaultdict, Counter
2def twoSumsMap(nums: List[int]) -> Dict[int, Tuple[int, int]]:
3 two_sums_map = defaultdict(set)
4 for i, val_one in enumerate(nums):
5 for j, val_two in enumerate(nums[i+1:]):
6 two_sums_map[val_one + val_two].add(
7 (val_one, val_two)
8 if val_one <= val_two else
9 (val_two, val_one)
10 )
11 return two_sums_map
12def threeSum(nums: List[int]) -> List[List[int]]:
13 # O(n^2)
14 two_sums_map = self.twoSumsMap(nums)
15 # O(n)
16 counter_for_nums = Counter(nums)
17 three_sums = {}
18 # iterating on the dictionary instead of `nums` in order to avoid duplicative work
19 for curr_val in counter_for_nums.keys():
20 two_sum_tuples_for_val = two_sums_map[-curr_val]
21 for val_one, val_two in two_sum_tuples_for_val:
22 if (curr_val != val_one and curr_val != val_two) or counter_for_nums[curr_val] >= 3:
23 sorted_vals = sorted([curr_val, val_one, val_two])
24 three_sums[str(sorted_vals)] = sorted_vals
25 return three_sums.values()Time/Space Complexity
- Time Complexity:
O(n²) - Space Complexity:
O(n²)
3. Sorting, Iterating and Two Point
When given a list of strings or numbers during an algorithms interview we should always pause to consider whether sorting the input would allow the problem to be solved in a more efficient way, and in this case the answer is yes.
Consider the following array: [-2, 3, 1, 7, -4, 9]
And the same array sorted: [-4, -2, 1, 3, 7, 9]
When iterating over an array we should also pause to consider whether adding a second pointer, known as the "two pointers" approach, would be helpful.
In this case we can design an algorithm that combines both of the approaches above. We first sort the array, then iterate over it (index I), placing two pointers (L and R) at the beginning and end of the other already-sorted numbers. To iterate the two pointers, we can conditionally moving either the left or right pointer based on whether the current triplet sum is larger or smaller than zero. If at any point arr[I] + arr[L] + arr[R] = 0 that means we have found a triplet that sums to zero.
I L R
[-4, -2, 1, 3, 7, 9] arr[I] (-4) + arr[L] (-2) + arr[R] (9) = 3, which is >= 0 --> move right pointer
I L R
[-4, -2, 1, 3, 7, 9] arr[I] (-4) + arr[L] (-2) + arr[R] (7) = 1, which is >= 0 --> move right pointer again
I L R
[-4, -2, 1, 3, 7, 9] arr[I] (-4) + arr[L] (-2) + arr[R] (3) = -3, which is <= 0 --> move left pointer
I L R
[-4, -2, 1, 3, 7, 9] arr[I] (-4) + arr[L] (1) + arr[R] (3) = 0, we found a match! Then move left pointer
I LR
[-4, -2, 1, 3, 7, 9] L = R, while loop no longer true, iterate `I`
I L R
[-4, -2, 1, 3, 7, 9] arr[I] (-2) + arr[L] (3) + arr[R] (9) = 10, which is >= 0 --> move right pointer
etc.1 I L R
2[-4, -2, 1, 3, 7, 9] arr[I] (-4) + arr[L] (-2) + arr[R] (9) = 3, which is >= 0 --> move right pointer
3 I L R
4[-4, -2, 1, 3, 7, 9] arr[I] (-4) + arr[L] (-2) + arr[R] (7) = 1, which is >= 0 --> move right pointer again
5 I L R
6[-4, -2, 1, 3, 7, 9] arr[I] (-4) + arr[L] (-2) + arr[R] (3) = -3, which is <= 0 --> move left pointer
7 I L R
8[-4, -2, 1, 3, 7, 9] arr[I] (-4) + arr[L] (1) + arr[R] (3) = 0, we found a match! Then move left pointer
9I LR
10[-4, -2, 1, 3, 7, 9] L = R, while loop no longer true, iterate `I`
11 I L R
12[-4, -2, 1, 3, 7, 9] arr[I] (-2) + arr[L] (3) + arr[R] (9) = 10, which is >= 0 --> move right pointer
13etc.Three Sum Python and JavaScript Solutions - Two Sum Hashmap
def threeSum(self, nums: List[int]) -> List[List[int]]:
sorted_nums = sorted(nums)
three_sums = []
for i in range(len(sorted_nums)):
# avoid duplicates
if i > 0 and sorted_nums[i] == sorted_nums[i - 1]:
continue
target = -sorted_nums[i]
l, r = i + 1, len(sorted_nums) - 1
while l < r:
if sorted_nums[l] + sorted_nums[r] == target:
three_sums.append([sorted_nums[i], sorted_nums[l], sorted_nums[r]])
l += 1
# avoid duplicates again
while l < r and sorted_nums[l] == sorted_nums[l - 1]:
l += 1
elif sorted_nums[l] + sorted_nums[r] < target:
l += 1
else:
r -= 1
return three_sums1def threeSum(self, nums: List[int]) -> List[List[int]]:
2 sorted_nums = sorted(nums)
3 three_sums = []
4 for i in range(len(sorted_nums)):
5 # avoid duplicates
6 if i > 0 and sorted_nums[i] == sorted_nums[i - 1]:
7 continue
8 target = -sorted_nums[i]
9 l, r = i + 1, len(sorted_nums) - 1
10 while l < r:
11 if sorted_nums[l] + sorted_nums[r] == target:
12 three_sums.append([sorted_nums[i], sorted_nums[l], sorted_nums[r]])
13 l += 1
14 # avoid duplicates again
15 while l < r and sorted_nums[l] == sorted_nums[l - 1]:
16 l += 1
17 elif sorted_nums[l] + sorted_nums[r] < target:
18 l += 1
19 else:
20 r -= 1
21 return three_sumsTime/Space Complexity
- Time Complexity:
O(n²) - Space Complexity:
O(n)(orO(1)if sorted in-place)
Watch Mock Interviews Featuring the Three Sum Question
Practice Questions Similar to Three Sum
About interviewing.io
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.
We know exactly what to do and say to get the company, title, and salary you want.
Interview prep and job hunting are chaos and pain. We can help. Really.
