3Sum
Last Updated: April 2, 2026
Understanding the Problem
We need to find all unique triplets (three elements) in the array that add up to zero. Two key things make this harder than Two Sum.
First, we need all valid triplets, not just one. Second, we need to avoid duplicate triplets in our result. For example, if the array has two -1s, both [-1, 0, 1] using the first -1 and [-1, 0, 1] using the second -1 count as the same triplet. We only want it once.
The core insight is this: if we fix one element nums[i], we need the other two elements to sum to -nums[i]. That's exactly the Two Sum problem. So 3Sum reduces to running Two Sum for each element in the array.
Key Constraints:
3 <= nums.length <= 3000→ With n up to 3000, O(n^2) gives us about 9 million operations, which is fine. O(n^3) gives 27 billion, which is too slow.-10^5 <= nums[i] <= 10^5→ Values fit in a standard integer. No overflow concerns for sums of three elements.
Approach 1: Brute Force
Intuition
The most straightforward approach is to check every possible combination of three elements. For each triplet (i, j, k), check if nums[i] + nums[j] + nums[k] == 0. If it does, add it to the result.
The tricky part is handling duplicates. We can sort each found triplet and store it in a set to ensure uniqueness. This way, [-1, 0, 1] and [0, -1, 1] both normalize to [-1, 0, 1] and the set catches the duplicate.
Algorithm
- Initialize an empty set to store unique triplets.
- Use three nested loops to iterate over all combinations of indices
(i, j, k)wherei < j < k. - For each combination, check if
nums[i] + nums[j] + nums[k] == 0. - If the sum is zero, sort the triplet and add it to the set.
- Convert the set to a list and return.
Example Walkthrough
Code
- Time Complexity: O(n^3). Three nested loops, each iterating up to n times. Sorting each triplet is O(1) since it's always 3 elements. Set operations add some overhead but don't change the cubic nature.
- Space Complexity: O(n). The set stores unique triplets. In the worst case, the number of valid triplets is O(n^2), but typically much smaller.
The brute force checks every possible combination, which is far too slow for n up to 3000. If we fix one element and reduce the problem to Two Sum, can we find pairs more efficiently using a hash set?
Approach 2: Hash Set
Intuition
Here's the key insight: if we fix one element nums[i], we need two other elements that sum to -nums[i]. That's literally the Two Sum problem. And we know Two Sum can be solved in O(n) using a hash set.
So the plan is: for each element nums[i], run a Two Sum search on the remaining elements looking for pairs that sum to -nums[i]. We use a hash set to find complements in O(1).
For duplicate avoidance, we first sort the array. Then we skip over duplicate values for the outer loop. For the inner Two Sum, we also need to be careful about adding duplicate triplets, which we handle by checking against the last triplet we added.
Algorithm
- Sort the array.
- For each index
ifrom 0 to n-3: - Skip if
nums[i]is the same asnums[i-1](avoid duplicate first elements). - Set
target = -nums[i]. - Use a hash set to find pairs in
nums[i+1...n-1]that sum totarget. - For each
nums[j], computecomplement = target - nums[j]. - If complement is in the set, we found a valid triplet. Add it and skip duplicates for
j. - Otherwise, add
nums[j]to the set. - Return the result.
Example Walkthrough
Code
- Time Complexity: O(n^2). Sorting takes O(n log n). The outer loop runs n times, and for each iteration, the inner loop runs up to n times with O(1) hash set operations. Total: O(n log n + n^2) = O(n^2).
- Space Complexity: O(n). The hash set stores up to n elements in each iteration of the outer loop.
This approach is already O(n^2), which is optimal for this problem. But we're using O(n) extra space for the hash set in each iteration. Can we achieve the same time complexity without the hash set by using two pointers on the sorted array?
Approach 3: Sorting + Two Pointers (Optimal)
Intuition
Since we need to sort the array anyway (for duplicate handling), we can take full advantage of the sorted order. After fixing nums[i], we need two elements in the remaining sorted subarray that sum to -nums[i]. In a sorted array, finding a pair with a given sum is a classic two-pointer problem.
Place one pointer left at the start of the remaining subarray (i+1) and another pointer right at the end. If the sum of the three elements is too small, move left right to increase it. If it's too large, move right left to decrease it. If it's exactly zero, we found a triplet.
The beauty of this approach is that each pointer moves in only one direction, so the inner search is O(n). Combined with the outer loop, we get O(n^2) total with O(1) extra space.
The two-pointer technique works because the array is sorted. When the sum is too small, moving the left pointer right increases it (since nums[left+1] >= nums[left]). When the sum is too large, moving the right pointer left decreases it. This monotonic property guarantees that we don't miss any valid pairs. Each pointer moves at most n times total, so the inner loop is O(n) for each fixed i.
The duplicate skipping works because, in a sorted array, duplicate values are adjacent. After finding a valid triplet, we skip all copies of nums[left] and nums[right] before moving on. For the outer loop, we skip duplicate values of nums[i] for the same reason. This guarantees every triplet in the result is unique.
Algorithm
- Sort the array.
- For each index
ifrom 0 to n-3: - If
nums[i] > 0, break (since the array is sorted, no three positive numbers can sum to zero). - Skip if
nums[i]equalsnums[i-1](avoid duplicate first elements). - Set
left = i + 1andright = n - 1. - While
left < right: - Compute
sum = nums[i] + nums[left] + nums[right]. - If
sum < 0, incrementleft(need a larger value). - If
sum > 0, decrementright(need a smaller value). - If
sum == 0, add the triplet, then skip duplicates for bothleftandright. - Return the result.
Example Walkthrough
Code
- Time Complexity: O(n^2). Sorting takes O(n log n). The outer loop runs n times, and the two-pointer inner loop runs O(n) times for each iteration. Total: O(n log n + n^2) = O(n^2).
- Space Complexity: O(1) (ignoring the output and sort space). We only use a few pointer variables. The sort may use O(log n) stack space depending on the implementation.