Loading...
Master the 3Sum problem with Sort + Two Pointers, avoid the duplicate-skipping traps that trip up most candidates, and learn the pattern that unlocks a whole class of interview questions.
Here's the thing ā when an interviewer asks you 3Sum, they're not just testing whether you memorized the solution. They're watching how you think. Can you recognize that brute force is too slow? Can you articulate why sorting helps? Do you handle edge cases without being prompted?
I've seen candidates who knew the answer cold but still failed because they couldn't explain their duplicate-skipping logic. And I've seen candidates who didn't know the optimal solution upfront but reasoned their way there and crushed it.
Let's make sure you're in the second group ā but also know the solution. Best of both worlds.
Given an integer array nums, return all unique triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, j != k, and nums[i] + nums[j] + nums[k] == 0.
The tricky word there is unique. You can't return duplicate triplets ā and that's where most people get burned.
Example:
Input: nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]Before we even touch code, understand what signals the interviewer is looking for:
l vs r without being asked?A strong answer walks through your reasoning out loud. A weak answer is silent typing followed by "I think this works?"
Always acknowledge brute force ā but don't dwell on it. Show the interviewer you know it exists and why it's not good enough.
// Brute Force ā O(nĀ³), DO NOT submit this
// Use a Set to deduplicate, iterate all triplets
Set<List<Integer>> seen = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
for (int k = j + 1; k < nums.length; k++) {
if (nums[i] +
Say something like: "The brute force is O(nĀ³) ā we check every possible triplet. That's going to be way too slow for large inputs. I want to get this down to O(nĀ²), and I think sorting plus two pointers gets us there."
That one sentence tells the interviewer a lot about how you think.
Here's the core insight: if you sort the array first, you turn a 3-variable problem into a 2-variable problem. Fix one element nums[i], then use two pointers to find a pair that sums to -nums[i].
Why sorting helps:
nums[i] > 0, no valid triplet can exist)Let's walk through the algorithm step by step:
i from 0 to n-3i if it's a duplicate of the previous elementnums[i] > 0l = i + 1, r = n - 1l 0 ā move r` leftclass Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
// Skip duplicate values for the fixed element
if (i > 0 && nums[i] == nums[i - 1]) continue;
// Early termination: sorted array, nothing after can sum to 0
if (nums[i] >
Notice every piece of this has a reason. Let's break down the parts interviewers will probe.
This is the section you need to read twice. These are the exact moments I've watched candidates unravel in real interviews.
This is the #1 mistake I see ā and it's subtle enough that many candidates don't catch it in their own code.
Wrong:
while (l < r && nums[l] == nums[l + 1]) l++;
while (l < r && nums[r] == nums[r - 1]) r--;Correct:
while (l < r && nums[l] == nums[l - 1]) l++;
while (l < r && nums[r] == nums[r + 1]) r--;Here's why: you already moved l forward and r backward when you found the valid triplet. Now you're checking whether the new position is a duplicate of where you just came from. Comparing with l+1 or r-1 would compare against values you haven't visited yet ā that's comparing in the wrong direction entirely.
If an interviewer catches you doing this wrong, don't panic. Say: "Good catch ā let me think about that. After moving l++ and r--, I'm now at a new position. To skip duplicates, I need to compare the current value against the one I just left behind, not the one ahead. So it should be nums[l] == nums[l-1]..." Walking through your reasoning out loud recovers a lot of trust.
A common bug looks like this:
while (r > nums.length) // This is NEVER true, infinite loop or no executionAlways use while (l < r) as your loop condition. It's clean, correct, and easy to explain.
i#Without if (i > 0 && nums[i] == nums[i - 1]) continue;, you'll generate duplicate triplets for repeated values of nums[i]. For example, with [-1, -1, 0, 1, 2], you'd process -1 twice and return [-1, 0, 1] twice.
The interviewer will almost always test this with an array that has duplicate elements. Expect it.
After recording a valid triplet, if you only move one pointer:
// Bug: only moving l
result.add(...);
l++;
// r stays in place ā you'll re-examine the same elementYou either get an infinite loop or duplicate results. Always do l++; r--; together.
Forgetting if (nums[i] > 0) break; won't give you wrong answers ā but it will make your solution slower than it needs to be, and in an interview, an interviewer might probe: "Can we optimize this further?" If you didn't add early termination, that's a signal you're not thinking about all the properties of the sorted array.
Here's how an ideal candidate narrates this problem. Practice saying this out loud ā seriously, it matters.
"Okay, so I need to find all unique triplets that sum to zero. My first instinct is brute force ā try every combination of three elements, that's O(nĀ³). But that's going to be too slow for large inputs, so let me think about how to reduce this.
One approach that comes to mind: if I sort the array, I can fix one element and reduce the problem to Two Sum on the remaining elements ā which I can solve with two pointers in O(n). Doing that for each element gives me O(nĀ²) overall, which is a big improvement.
Let me code this up. I'll iterate i from 0 to n-1, use l = i+1 and r = n-1 as my two pointers, and adjust based on whether the sum is too small or too large.
The tricky part is handling duplicates. I need to skip duplicate values for i, and after finding a valid triplet, I need to skip duplicate values for both l and r. The key thing there is to compare with the previous position after moving ā not the next one.
One more optimization: since the array is sorted, if nums[i] is positive, no triplet can sum to zero, so I can break early."
That's what a strong answer sounds like. You show awareness of complexity, justify your choices, and flag the subtle parts proactively.
Never assume the problem ends when you write the code. Here's what interviewers typically ask next:
| Complexity | Value | Why |
|---|---|---|
| Time | O(nĀ²) | Sorting is O(n log n), two-pointer loop is O(nĀ²) overall |
| Space | O(1) | No extra data structures (excluding the output list) |
Be ready to explain both. If you use a HashSet for deduplication instead of the pointer approach, your space complexity becomes O(n) ā and interviewers will ask if you can do better.
Yes ā add another outer loop. Fix two elements, use two pointers for the rest. O(nĀ³) total. Same duplicate-skipping logic applies. This is exactly why I said 3Sum is a template.
Almost nothing changes ā replace == 0 with == k and adjust your early termination condition. This is a great chance to say: *"The pattern generalizes cleanly ā sort, fix one element, two pointers for the remainder against a target of k - nums[i]."
You can ā but it trades O(1) extra space for O(n) and adds overhead. The pointer approach is cleaner and more impressive. Say this clearly.
Here's the meta-lesson from 3Sum. Whenever you see a problem involving:
...your instinct should immediately be: Sort + Two Pointers + Duplicate Handling.
This template applies directly to:
When you can say in an interview, "This looks like the 3Sum pattern ā I think sorting and two pointers will work here", you're demonstrating pattern recognition, which is exactly what senior engineers at FAANG companies are looking for.
[-1, 0, 1, 2, -1, -4] by hand after writing. Catch your own bugs before the interviewer does.nums.length < 3? What if all elements are positive? Mention these even if you don't add explicit guards.Here's what to lock in before your next interview:
i with if (i > 0 && nums[i] == nums[i-1]) continuel++; r--;l and r by comparing backward: nums[l] == nums[l-1] and nums[r] == nums[r+1]if (nums[i] > 0) breakGet this pattern into your muscle memory. Once you can solve 3Sum cleanly and explain every line of it, a whole family of interview problems just got a lot easier.