3Sum

Question

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.

Example:

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].
Notice that the order of the output and the order of the triplets does not matter.

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.

Solution

For this question, we need to reduce into TwoSum (Two Pointers way)

So far we can figure out that the best possible complexity would be $O(n^2)$.

So if we can get 1 number as a pivot. We can have the other 2 numbers implemented as TwoSum (Two Pointers way).

This works out because given in the question that we need to avoid duplication. Which means the array needs to be sorted so that if we have already traversed 1 element, we will skip if we see that element again (this concept is the same as Subset > ^d9061d)

Once we sorted it, it gives us benefit for TwoSum (Two Pointers way)

Implementation

class App:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        if len(nums) < 3: return []
        nums.sort()
        
        result = []
        for pivot in range(len(nums)):
            if pivot > 0 and nums[pivot] == nums[pivot - 1]:
                # Have already done for this pivot
                continue
            
            currentNumber = nums[pivot]
            left, right = pivot + 1, len(nums) - 1
            
            while (left < right):
                currentSum = currentNumber + nums[left] + nums[right]
                
                if (currentSum == 0):
                    result.append([currentNumber, nums[left], nums[right]])
                    
                    left += 1
                    right -= 1
                    
                    while (left < right) and (nums[left] == nums[left - 1]) and (nums[right] == nums[right + 1]):
                        # We have already selected these 3 numbers, gotta skip
                        left += 1
                        right -= 1
                elif currentSum < 0:
                    # increase left to increase sum
                    left += 1
                else:
                    # decrease right to decrease sum
                    right -= 1
            
        return result