Problem Statement

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Additional information

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

Example 1:

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

Output: [[-1, -1, 2], [-1, 0, 1]]

Example 2:

Input: nums = [0, 1, 1]

Output: []

Example 3:

Input: nums = [0, 0, 0]

Output: [[0, 0, 0]]

Brute Force

Intuition
The most straightforward approach is to check every possible combination of three numbers. We can use three nested loops to pick nums[i], nums[j], and nums[k]. If their sum is zero, we sort the triplet and add it to a set to avoid duplicates. Finally, convert the set to a list.

Algorithm

1. Initialize a set res to store unique triplets.
2. Iterate i from 0 to n-1.
3. Iterate j from i + 1 to n-1.
4. Iterate k from j + 1 to n-1.
5. If nums[i] + nums[j] + nums[k] == 0, create a tuple of the sorted values and add it to res.
6. Return the list of tuples converted to lists.

def three_sum(nums: list[int]) -> list[list[int]]:
    res = set()
    nums.sort()
    n = len(nums)
    
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                if nums[i] + nums[j] + nums[k] == 0:
                    res.add((nums[i], nums[j], nums[k]))
                    
    return [list(x) for x in res]

Time & Space Complexity

• Time complexity: O(n^3)

• Reason: Three nested loops iterating through the array.

• Space complexity: O(n)

• Reason: Storing the output results.

Sorting + Two Pointers (Optimal)

Intuition
We can reduce the problem to the "Two Sum II" problem. First, we sort the array. Then, we iterate through the array with a fixed pointer i. For each i, we need to find two other numbers (using pointers l and r) such that nums[l] + nums[r] = -nums[i]. Because the array is sorted, we can use the two-pointer approach to find these pairs efficiently in O(n) time. The sorting also allows us to easily skip duplicates to ensure unique triplets.

Algorithm

1. Sort the array nums.
2. Iterate through the array with index i.
3. Skip Duplicates: If i > 0 and nums[i] == nums[i-1], continue to the next iteration to avoid duplicate triplets.
4. Initialize l = i + 1 and r = len(nums) - 1.
5. While l < r:

• Calculate three_sum = nums[i] + nums[l] + nums[r].
• If three_sum > 0: Decrement r to reduce the sum.
• If three_sum < 0: Increment l to increase the sum.
• If three_sum == 0:
• Add [nums[i], nums[l], nums[r]] to the result.
• Increment l to look for other pairs.
• Skip Duplicates: While l < r and nums[l] == nums[l-1], increment l again to avoid picking the same second number.

def three_sum(nums: list[int]) -> list[list[int]]:
    res = []
    nums.sort()

    for i, a in enumerate(nums):
        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
                while l < r and nums[l] == nums[l - 1]:
                    l += 1
    return res

Time & Space Complexity

• Time complexity: O(n^2)

• Reason: Sorting takes O(n log n). The outer loop runs n times, and the inner two-pointer loop runs in O(n) time. Total is O(n^2).

• Space complexity: O(1) or O(n)

• Reason: Depends on the sorting implementation. We only use pointers for the algorithm itself.