3Sum

Problem Statement

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] where nums[i] + nums[j] + nums[k] == 0, and the indices i, j and k are all distinct.

The output should not contain any duplicate triplets. You may return the output and the triplets in any order.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Explanation: nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0. nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0. nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0. The distinct triplets are [-1,0,1] and [-1,-1,2].

Example 2:

Input: nums = [0,1,1]
Output: []

Explanation: The only possible triplet does not sum up to 0.

Example 3:

Input: nums = [0,0,0]
Output: [[0,0,0]]

Explanation: The only possible triplet sums up to 0.

Constraints:

  • 3 <= nums.length <= 1000
  • -10^5 <= nums[i] <= 10^5

You should aim for a solution with O(n^2) time and O(1) space, where n is the size of the input array.

You should aim for a solution with O(n^2) time and O(1) space, where n is the size of the input array.

Hint 1

A brute force solution would be to check for every triplet in the array. This would be an O(n^3) solution. Can you think of a better way?

Hint 2

Can you think of an algorithm after sorting the input array? What can we observe by rearranging the given equation in the problem?

Hint 3

We can iterate through nums with index i and get nums[i] = -(nums[j] + nums[k]) after rearranging the equation, making -nums[i] = nums[j] + nums[k]. For each index i, we should efficiently calculate the j and k pairs without duplicates. Which algorithm is suitable to find j and k pairs?

Hint 4

To efficiently find the j and k pairs, we run the two pointer approach on the elements to the right of index i as the array is sorted. When we run two pointer algorithm, consider j and k as pointers (j is at left, k is at right) and target = -nums[i], if the current sum num[j] + nums[k] < target then we need to increase the value of current sum by incrementing j pointer. Else if the current sum num[j] + nums[k] > target then we should decrease the value of current sum by decrementing k pointer. How do you deal with duplicates?

Hint 5

When the current sum nums[j] + nums[k] == target add this pair to the result. We can move j or k pointer until j < k and the pairs are repeated. This ensures that no duplicate pairs are added to the result.

Solution

Brute Force

def three_sum_brute_force(nums: List[int]) -> List[List[int]]:
res = set()
nums.sort()
for i in range(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:
tmp = [nums[i], nums[j], nums[k]]
res.add(tuple(tmp))
return [list(i) for i in res]

Time complexity: O(n^3) Space complexity: O(m)

Hash Map

from collections import defaultdict
def three_sum_hash_map(nums: List[int]) -> List[List[int]]:
nums.sort()
count = defaultdict(int)
for num in nums:
count[num] += 1
res = []
for i in range(len(nums)):
count[nums[i]] -= 1
if i and nums[i] == nums[i - 1]:
continue
for j in range(i + 1, len(nums)):
count[nums[j]] -= 1
if j - 1 > i and nums[j] == nums[j - 1]:
continue
target = -(nums[i] + nums[j])
if count[target] > 0:
res.append([nums[i], nums[j], target])
for j in range(i + 1, len(nums)):
count[nums[j]] += 1
return res

Time complexity: O(n^2) Space complexity: O(n)

Two Pointers

def three_sum_two_pointers(nums: List[int]) -> List[List[int]]:
res = []
nums.sort()
for i, a in enumerate(nums):
if a > 0:
break
if i > 0 and a == nums[i - 1]:
continue
l, r = i + 1, len(nums) - 1
while l < r:
three_sum = a + nums[l] + nums[r]
if three_sum > 0:
r -= 1
elif three_sum < 0:
l += 1
else:
res.append([a, nums[l], nums[r]])
l += 1
r -= 1
while nums[l] == nums[l - 1] and l < r:
l += 1
return res

Time complexity: O(n^2) Space complexity: O(1)