MEDIUM
DATA STRUCTURES AND ALGORITHMS

# How to solve the Three Sum Problem

ARRAYSSORTINGHASH MAPSSEARCH
Written By
Tom Wagner
Kenny Polyak

## Introduction Three Sum

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.

## Problem Three Sum

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.

## Solution Three Sum

Watch Someone Solve Three Sum
FireEye InterviewJava Interview
Advance this person to the next round?
Technical Skills:
3/4
Problem Solving Ability:
3/4
Communication Ability:
3/4
Show Transcript

### Three Sum Problem Approaches

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:
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]]``````

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:]):
(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()``````

#### 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.``````

#### 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_sums``````

#### Time/Space Complexity

• Time Complexity: `O(n²)`
• Space Complexity: `O(n)` (or `O(1)` if sorted in-place)

## Practice Questions Similar to Three Sum

MEDIUM
Data Structures and Algorithms
Build a Max Heap

Given an array of integers, transform the array in-place to a max heap.

Watch 1 interview
EASY
Data Structures and Algorithms

Watch 2 interviews
MEDIUM
Data Structures and Algorithms
Container With Most Water

Given n non-negative integers, find two lines that form a container that can hold the most amount of water.

Watch 1 interview