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.

Recommended Time and Space Complexity

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)