3Sum | Leetcode 15

Welcome to our deep dive on 3Sum (Leetcode 15). Expanding upon the popular Two Sum problem, 3Sum demands extreme duplicate management since we must return uniquely distinct triplets.

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: nums = [-1, 0, 1, 2, -1, -4] => Output: [[-1, -1, 2], [-1, 0, 1]]

Approach: Target Fixing + Two Pointers O(N^2)

The key to optimizing 3Sum without brute-forcing every combination O(N^3) is to rely on Sorting.

1. Sort the array: Sorting allows us to easily skip duplicate values and use a highly efficient two-pointer squeeze on the remaining bounds.
2. Anchor the target: Iterate through the array. For every nums[i], anchor it as your target component. Crucially, if nums[i] == nums[i-1], we skip it to prevent generating duplicate identical triplets!
3. Squeeze Pointers: Fire a left pointer just above i, and a right pointer at the end of the array. Squeeze them inward based on whether the total sum is < 0 or > 0.
4. Skip Internal Duplicates: When a valid triplet is found, we must also aggressively bump the left pointer to bypass any identical adjacent values to avoid duplicate outputs.

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()
        
        for i in range(len(nums) - 2):
            # Bypass duplicate anchor candidates
            if i > 0 and nums[i] == nums[i - 1]:
                continue
                
            left = i + 1
            right = len(nums) - 1
            
            while left < right:
                total = nums[i] + nums[left] + nums[right]
                
                if total < 0:
                    left += 1
                elif total > 0:
                    right -= 1
                else:
                    res.append([nums[i], nums[left], nums[right]])
                    
                    # Bypass duplicate internal bounds
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1
                        
                    left += 1
                    right -= 1
                    
        return res

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (15)