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] is 0.

Notice that the solution set must not contain duplicate triplets.

Examples

1. For array [-1, 0, 1, 2, -1, -4] output will be [-1, -1, 2] and [-1, 0, 1]
2. For array [0, 1, 1], there are no triplets that have zero sum
3. For array [0, 0, 0], the output will be [0, 0, 0]

Solution

Points of Interest

1. Brute force method will be to consider all triplets in array and add them to results if not already there. Time complexity will be of $O(n^3)$.
2. Although there is an approach with which we can find a pair of elements in a sorted array with given sum in $O(n)$. Here we will use Two Pointer method.
3. We will first sort the array.
4. Then we choose one element and find other elements using this approach in sub-array after that element.
5. This will have time complexity of $O(n^2)$.

Algo

As mentioned above we will use a modified version of Two Pointer method to solve the 2 sum problem for each element of the array.

1. Initialize results array, that will contain all such triplets.
2. Sort array in increasing order.
3. Iterate over array to get 1st element at $i^{th}$ index. Now our problem is to find a pair of values in $(i, N-1]$ array whose sum is the negative of nums[i]. For that:
   1. Initialize start and end as i+1 and n - 1.
   2. Loop until start is less than end.
      1. If sum of start and end elements is greater than negative of nums[i], move the end pointer.
      2. If sum of start and end elements is less than negative of nums[i], move the start pointer.
      3. Else, insert the triplet into the results and keep moving the start pointer such that its value is different than initial start value.
4. Here you will have all the eligible triplets from nums arrays in results array.

Code

def threeSum(nums: list[int]) -> list[list[int]]:
    results = list()
    nums.sort()

    for i, val in enumerate(nums):
        if i > 0 and val == nums[i-1]:
            continue

        start, end = i + 1, len(nums) - 1
        while start < end:
            s = nums[start] + nums[end]
            if s > -val:
                end -= 1
            elif s < -val:
                start += 1
            else:
                results.append([val, nums[start], nums[end]])
                start += 1
                while start < len(nums) and nums[start] == nums[start - 1]:
                    start += 1
    
    return results

Complexity

$\textbf{Time Complexity} = O(N\log{N} + N(N + 1))$

• Sorting of array takes $N\log{N}$ time
• And finding a pair for first element at $i^{th}$ index takes (N - i) time. This adds up as $\sum_{0}^{N - 1}(N - i) = \frac{N(N + 1)}{2}$

$\textbf{Space Complexity} = O(1)$

• Sorting is done in place and we only use few variables, size of which is not dependent on the size of array.