Free lesson · DSA Mastery - Interview Prep, End to End
3Sum
3Sum
3Sum is one of the most important interview problems. It's a step up from Two Sum, and it teaches the sort-then-two-pointer pattern that generalizes to 4Sum and beyond. The clean solution sorts the array, fixes one element with an outer loop, and uses opposite-direction two pointers for the remaining pair - reducing what looks like O(n³) to O(n²).
The fiddly part is skipping duplicates to avoid returning the same triplet multiple times. Getting that logic exactly right is what separates a working solution from a buggy one, and it's a frequent source of interview mistakes.
The Problem
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:
-1 + 0 + 1 = 0
-1 + -1 + 2 = 0
(The triplet [0, 1, -1] is the same as [-1, 0, 1], so it's not duplicated.)
Example 2:
Input: nums = [0, 1, 1]
Output: []
Explanation: No triplet sums to 0.
Example 3:
Input: nums = [0, 0, 0]
Output: [[0, 0, 0]]
Constraints:
3 <= nums.length <= 3000-10^5 <= nums[i] <= 10^5
Approach
Interactive animation: One inner scan: fix -4, and every check rules out a row of pairs, because no pair reaches 4.
Step 1: Sort the array. Sorting enables two-pointer search and makes duplicate-skipping straightforward.
Step 2: Fix one element, then Two Sum on the rest. For each index i, the problem reduces to finding two numbers in nums[i+1..n-1] that sum to -nums[i]. Since the array is sorted, use opposite-direction two pointers.
Step 3: Skip duplicates at three points:
- Skip duplicate values for the fixed element
i. - After finding a triplet, skip duplicate values for
left. - After finding a triplet, skip duplicate values for
right.
graph TD
A["Sort nums"] --> B["For i = 0 to n - 3"]
B --> C{"i > 0 AND nums[i] == nums[i-1]?"}
C -->|Yes| D["Skip duplicate i"]
C -->|No| E["left = i+1, right = n-1"]
E --> F{"left < right?"}
F -->|No| B
F -->|Yes| G["sum = nums[i] + nums[left] + nums[right]"]
G --> H{"sum vs 0"}
H -->|"== 0"| I["Add triplet<br/>skip dup left & right<br/>left++, right--"]
H -->|"< 0"| J["left++"]
H -->|"> 0"| K["right--"]
I --> F
J --> F
K --> F
D --> B
style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
style C fill:#b45309,stroke:#f59e0b,color:#f1f5f9
style E fill:#4338ca,stroke:#6366f1,color:#f1f5f9
style F fill:#b45309,stroke:#f59e0b,color:#f1f5f9
style G fill:#4338ca,stroke:#6366f1,color:#f1f5f9
style H fill:#b45309,stroke:#f59e0b,color:#f1f5f9
style I fill:#16a34a,stroke:#10b981,color:#f1f5f9
style J fill:#4338ca,stroke:#6366f1,color:#f1f5f9
style K fill:#4338ca,stroke:#6366f1,color:#f1f5f9
style D fill:#b45309,stroke:#f59e0b,color:#f1f5f9
This diagram shows the sort-then-two-pointer approach. After sorting, we fix each element with an outer loop, skipping duplicates. For each fixed element, we use two pointers to find pairs in the remaining sorted subarray that sum to the negation of the fixed element. When we find a triplet, we record it and skip duplicate values on both pointers.
An Early-Exit Optimization
After sorting, if nums[i] > 0, then since nums[left] and nums[right] are both >= nums[i] > 0, their sum can't be zero. We can break out of the outer loop entirely. This is a small optimization but worth mentioning.
Code Implementation
public static List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
int n = nums.length;
for (int i = 0; i < n - 2; i++) {
// Early exit: smallest is positive, no zero-sum triplet possible
if (nums[i] > 0) break;
// Skip duplicate fixed elements
if (i > 0 && nums[i] == nums[i - 1]) continue;
int left = i + 1, right = n - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
result.add(Arrays.asList(nums[i], nums[left], nums[right]));
// Skip duplicates for left and right
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}
// Usage:
// System.out.println(threeSum(new int[]{-1, 0, 1, 2, -1, -4})); // [[-1, -1, 2], [-1, 0, 1]]
// System.out.println(threeSum(new int[]{0, 1, 1})); // []
// System.out.println(threeSum(new int[]{0, 0, 0})); // [[0, 0, 0]]
This Java code implements 3Sum. We sort the array, then fix each element with an outer loop, skipping duplicates and breaking early when the fixed element is positive. For each fixed element, we use two pointers to find pairs summing to its negation. When a triplet is found, we record it and skip duplicate values on both pointers before advancing.
The duplicate-skipping is the trickiest part:
The outer skip (nums[i] == nums[i-1]) ensures we don't process the same fixed value twice.
The inner skips (after finding a triplet) advance past consecutive equal values so we don't record the same triplet again. After skipping, we still do one more left++ and right-- to move to genuinely new values.
Interactive animation: The tempting one-line change: compare with the next value instead of the previous one.
Walkthrough
Interactive animation: Step through three loops with a set, then sort, fix one and converge two pointers.
Trace on nums = [-1, 0, 1, 2, -1, -4].
Sort: nums = [-4, -1, -1, 0, 1, 2]. n = 6.
i=0 (nums[0]=-4):
nums[0]=-4 > 0? No. i > 0? No.
left=1, right=5.
sum = -4 + (-1) + 2 = -3. < 0. left++ → left=2.
sum = -4 + (-1) + 2 = -3. < 0. left++ → left=3.
sum = -4 + 0 + 2 = -2. < 0. left++ → left=4.
sum = -4 + 1 + 2 = -1. < 0. left++ → left=5.
left=5, right=5. left < right? No. Done with i=0.
i=1 (nums[1]=-1):
nums[1]=-1 > 0? No. i > 0 AND nums[1]==nums[0]? -1 == -4? No.
left=2, right=5.
sum = -1 + (-1) + 2 = 0. Found! Add [-1, -1, 2].
Skip dup left: nums[2]=-1, nums[3]=0. Not equal. No skip.
Skip dup right: nums[5]=2, nums[4]=1. Not equal. No skip.
left++ → left=3. right-- → right=4.
sum = -1 + 0 + 1 = 0. Found! Add [-1, 0, 1].
Skip dup left: nums[3]=0, nums[4]=1. Not equal. No skip.
Skip dup right: nums[4]=1, nums[3]=0. Not equal. No skip.
left++ → left=4. right-- → right=3.
left=4, right=3. left < right? No. Done with i=1.
i=2 (nums[2]=-1):
i > 0 AND nums[2]==nums[1]? -1 == -1? Yes. Skip (continue).
i=3 (nums[3]=0):
nums[3]=0 > 0? No. nums[3]==nums[2]? 0 == -1? No.
left=4, right=5.
sum = 0 + 1 + 2 = 3. > 0. right-- → right=4.
left=4, right=4. Done.
i=4: i < n-2 = 4? No (i must be < 4). Loop ends.
Result: [[-1, -1, 2], [-1, 0, 1]].
Result: [[-1, -1, 2], [-1, 0, 1]].
Complexity Analysis
| Aspect | Complexity | Notes |
|---|---|---|
| Time | O(n²) | Sort O(n log n) + outer loop O(n) × two pointers O(n) |
| Space | O(1) or O(n) | Excluding output; depends on sort implementation |
Why It Is O(n²)
Sorting is O(n log n). The outer loop runs O(n) times. For each fixed element, the two-pointer scan is O(n). So the main work is O(n) × O(n) = O(n²), which dominates the O(n log n) sort.
Why Space Is O(1) Auxiliary
Excluding the output list, we use only index variables. (Java's Arrays.sort on primitives uses O(log n) stack space for the recursion, sometimes counted as O(log n).)
The output itself can be O(n²) in the worst case (many triplets), but that's required by the problem.
Variations & Follow-ups
What about 3Sum Closest?
Find the triplet whose sum is closest to a target (not necessarily zero). Track the best sum as you go; move pointers based on whether the current sum is below or above the target. O(n²).
What about 3Sum Smaller?
Count triplets with sum less than a target. For each fixed i, when nums[i] + nums[left] + nums[right] < target, all pairs between left and right also satisfy it - add right - left to the count and move left. O(n²).
What about 4Sum?
That's the next topic. Add another outer loop (fix two elements), then two pointers for the remaining pair. O(n³).
Can you avoid sorting and use hashing?
A hash-based approach exists but is messier to deduplicate and isn't faster asymptotically. Sorting + two pointers is the cleaner, standard solution.
What if you needed triplets summing to a target other than zero?
Replace the comparison sum == 0 with sum == target (and adjust the < / > branches accordingly). The structure is identical.
What about edge cases?
Interactive animation: Five zeros: after the first hit, left slides past every repeat, so [0, 0, 0] is added once.
- Fewer than 3 elements: No triplets. (Constraint says n >= 3.)
- All zeros: One triplet
[0, 0, 0]. Duplicate-skipping ensures it appears once. - No valid triplet: Returns empty list.
- All positive or all negative: No zero-sum triplet (early exit when smallest is positive; symmetric reasoning for all-negative - the loop just finds nothing).
- Many duplicates: The skip logic ensures each distinct triplet appears exactly once.
Common Interview Pitfalls
Interactive animation: Comparing with the next value skips the first -1, and [-1, -1, 2] is never found.
- Forgetting to skip duplicates. Without skipping, you'll return the same triplet multiple times. This is the #1 bug.
- Skipping duplicates incorrectly. The outer skip uses
nums[i] == nums[i-1](compare to the previous). The inner skips compare to the next value while moving. Mixing these up causes missed or duplicate triplets. - Not sorting first. Two pointers requires sorted input. The whole approach falls apart without it.
- Off-by-one in the outer loop.
i < n - 2(need room for left and right). - Using a hash set of triplets to dedupe. Works but is slower and uses extra space. The skip logic is cleaner.
- Forgetting the early exit. Not a correctness issue, but
if (nums[i] > 0) break;is a nice optimization.
Why This Problem Matters
3Sum is the bridge from Two Sum to the general k-Sum family. It teaches:
- Sort to enable two pointers. When the input isn't sorted but you need pair-finding, sorting first (and accepting O(n log n)) unlocks the technique.
- Reduce dimensionality by fixing elements. A 3-element search becomes "fix one + 2-element search." This generalizes: k-Sum is "fix one + (k-1)-Sum."
- Duplicate management. Skipping duplicates cleanly is a transferable skill.
The pattern appears in:
- 4Sum (next topic) - fix two, two-pointer the rest.
- k-Sum in general - recursive reduction to 2Sum.
- Subset-sum variants - when combined with other constraints.
If you can write 3Sum cleanly - including the duplicate skipping - you've demonstrated mastery of the sort-plus-two-pointer pattern. The next topic, 4Sum, extends it one dimension further.