Problem of The Day: 3Sum

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.

 

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

Intuition

My initial thoughts on how to solve this problem revolve around utilizing the two-pointer approach to efficiently explore triplets that sum to zero. Sorting the array allows us to efficiently navigate through different combinations.

Approach

My approach involves sorting the array to simplify the process of finding triplets that sum to zero. I iterate through the array and use two pointers (left and right) to explore possible triplets. I handle duplicates to avoid redundant solutions. Whenever the sum of the current triplet is zero, I add it to the result. I continue iterating and adjusting the pointers based on the comparison with zero.

Complexity

• Time complexity: O(n^2), where n is the length of the input array. The sorting step takes O(n log n) time, and the two-pointer approach involves a nested loop with linear time complexity.

• Space complexity: O(1) as we use a constant amount of space to store variables (res, num, l, r, curr_sum) without relying on additional data structures that scale with the input size.

Code

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res = []
        
        for i in range(len(nums) - 2):
            # Skip duplicates to avoid redundant solutions
            if i > 0 and nums[i - 1] == nums[i]:
                continue
            
            num, l, r = nums[i], i + 1, len(nums) - 1
            
            while l < r:
                curr_sum = num + nums[l] + nums[r]
                
                if curr_sum == 0:
                    res.append([num, nums[l], nums[r]])
                    l += 1
                    r -= 1

                    # Skip duplicates to avoid redundant solutions
                    while l < r and nums[l] == nums[l - 1]:
                        l += 1
                        
                elif curr_sum > 0:
                    r -= 1
                else:
                    l += 1
                
        return res

Editorial Solution

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()
        for i in range(len(nums)):
            if nums[i] > 0:
                break
            if i == 0 or nums[i - 1] != nums[i]:
                self.twoSumII(nums, i, res)
        return res

    def twoSumII(self, nums: List[int], i: int, res: List[List[int]]):
        lo, hi = i + 1, len(nums) - 1
        while (lo < hi):
            sum = nums[i] + nums[lo] + nums[hi]
            if sum < 0:
                lo += 1
            elif sum > 0:
                hi -= 1
            else:
                res.append([nums[i], nums[lo], nums[hi]])
                lo += 1
                hi -= 1
                while lo < hi and nums[lo] == nums[lo - 1]:
                    lo += 1

No sort Approach

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res, dups = set(), set()
        seen = {}
        for i, val1 in enumerate(nums):
            if val1 not in dups:
                dups.add(val1)
                for j, val2 in enumerate(nums[i+1:]):
                    complement = -val1 - val2
                    if complement in seen and seen[complement] == i:
                        res.add(tuple(sorted((val1, val2, complement))))
                    seen[val2] = i
        return res

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