0015.3Sum

Link: 15. 3Sum - Medium
Track: NeetCode150, Amazon

Question

• 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.

Restate

• Given an integer array
• Find all unique combinations of three numbers in nums that sum to 0.
• Return a list of all possible three triplets
  • The order of triplets does not matter
  • No duplicate triplets are allowed.

Edge Case

• n < 3, return []
• All zeros: [0,0,0,0] → [[0,0,0]]

---

Method	Approach	Time Complexity	Space Complexity
Method 1 ⭐	Two Pointers	$O(n^2)$	$O(1)$

Method 1 - Two Pointers

Sort the array. Fix i as the first number, then use two pointers to find pairs that sum to -nums[i].

Approach

1. Sort nums
2. For each index i from 0 .. n-3:
   • Skip duplicate i: if i>0 and nums[i]==nums[i-1], continue
   • Set left=i+1, right=n-1, target=-nums[i]
   • While left < right:
     • s = nums[left] + nums[right]
     • If s == target: record triplet, then move both pointers and skip duplicates
     • If s < target: left += 1
     • Else: right -= 1

Complexity

• Time Complexity: $O(n^2)$
  • Sort: $O(nlogn)$
• Space Complexity: O(1)
  • Ignore output

Code

class Solution:
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        nums.sort()
        n = len(nums)
 
        res = []
        for idx in range(n - 2):
            
            if idx > 0 and nums[idx] == nums[idx - 1]:
                continue
 
            target = -nums[idx]
            left = idx + 1
            right = n - 1
            while left < right:
                total = nums[left] + nums[right]
                
                if total == target:
                    res.append([nums[idx], nums[left], nums[right]])
                    left += 1
                    right -= 1
                    while left < right and nums[left] == nums[left - 1]:
                        left += 1
                    while left < right and nums[right] == nums[right + 1]:
                        right -= 1
                
                elif total < target:
                    left += 1
                
                else:
                    right -= 1
        
        return res

• Explain:
  • left < right means there are two distinct elements to use.
  • If you “skip duplicates” by checking if triplet in res before appending, the membership check is O(#results) each time, which can degrade the overall runtime.

---

Common Mistake

• Sorting at first
• Skip the duplicate after finding a valid result