15. 3Sum
Model: qwen3.5:9b
Topics: Array,Two Pointers
FAANG asked: 1
Acceptance rate: 28.3%
Problem Breakdown
We need to find all unique triplets within an integer array that sum up to zero.
- Inputs: An unsorted list of integers
nums. - Outputs: A list of lists, where each inner list represents a valid triplet
[a, b, c]such that . - Constraints & Edge Cases:
- The solution set must not contain duplicate triplets (e.g.,
[-1, 0, 1]is the same as[0, -1, 1]). - Indices of elements in a triplet must be distinct.
- Input can include negative numbers and zeros.
- Empty input or arrays with fewer than three elements should return an empty list immediately.
- The solution set must not contain duplicate triplets (e.g.,
Intuition
A naive brute-force approach uses three nested loops to check every combination . This runs in time complexity. Given the constraint nums.length <= 3000, this is too slow ( operations).
To improve efficiency, we can fix one number and solve for a “Two Sum” problem on the remaining subarray.
- Hashing Approach: Fix index , use a hash set to find pairs summing to
-nums[i]. This is time but requires extra space. Handling duplicates becomes messy because we need to track which indices were used and ensure unique triplets without storing too many states. - Two Pointers Approach: If we sort the array first, duplicate values are adjacent. We can fix index (the smallest number in a triplet) and use two pointers (
leftati+1,rightat end) to find pairs summing to-nums[i].- Since the array is sorted:
- If current sum < target, we need a larger value move
leftforward. - If current sum > target, we need a smaller value move
rightbackward. - This naturally handles duplicates by skipping identical values when moving pointers or iterating .
- If current sum < target, we need a larger value move
- Since the array is sorted:
Sorting takes , and the nested loop logic is effectively two passes over the array per outer iteration (). The sorting step simplifies duplicate handling significantly compared to hashing.
Approach
- Sort
numsin ascending order. This allows us to use binary search or two pointers and easily skip duplicates. - Iterate through the array with index
i. We stop atlen(nums) - 3because we need space for three elements (though iterating up ton-1works if logic handles bounds).- Optimization: If
nums[i] > 0, since the array is sorted, all subsequent numbers are positive. Their sum cannot be zero. Break early. - Duplicate Skip: If
i > 0andnums[i] == nums[i-1], skip this iteration to avoid generating duplicate triplets starting with the same number.
- Optimization: If
- Initialize two pointers:
left = i + 1andright = len(nums) - 1. - While
left < right:- Calculate sum of triplet.
- If sum == 0: Add to results. Move both pointers inward (
left++,right--). Crucially, skip any subsequent duplicate values for the new positions before continuing the loop check. - If sum < 0: Increment
left(need larger sum). - If sum > 0: Decrement
right(need smaller sum).
Complexity Analysis
- Time Complexity: . Sorting takes . The outer loop runs times, and the inner two-pointer scan is linear relative to the remaining elements. In worst case: .
- Space Complexity: auxiliary space if we ignore the output list storage (Python’s Timsort uses stack, but typically interviewers focus on algorithmic logic). The result set size depends on input distribution.
Solution
def threeSum(nums):
# Sort to handle duplicates and enable two-pointer technique
nums.sort()
n = len(nums)
res = []
for i in range(n - 2):
# Optimization: If current number is positive, no solution possible
# because array is sorted (all subsequent numbers are >= current).
if nums[i] > 0:
break
# Skip duplicates of the first element to avoid duplicate triplets
if i > 0 and nums[i] == nums[i - 1]:
continue
left, right = i + 1, n - 1
while left < right:
current_sum = nums[i] + nums[left] + nums[right]
if current_sum == 0:
res.append([nums[i], nums[left], nums[right]])
# Skip duplicates for the second element (left)
val_left = nums[left]
while left < right and nums[left] == val_left:
left += 1
# Skip duplicates for the third element (right)
val_right = nums[right]
while left < right and nums[right] == val_right:
right -= 1
elif current_sum < 0:
left += 1
else:
right -= 1
return res
Edge Cases Handled
- Empty Array / Length < 3: The loop
range(n - 2)handles this naturally (loop won’t execute), returning empty list. - All Positive Numbers: Optimization check (
nums[i] > 0) breaks early, preventing unnecessary computation and correctly returning an empty result set if no zeros/negatives exist to balance positives. - Duplicate Values in Input: The logic explicitly skips
iwhen it matches the previous element (outer loop) and skips subsequent identical elements forleft/rightpointers upon finding a match, ensuring unique triplets only.