You’re in a coding interview. The interviewer says: “Given an array of integers, find all unique triplets that sum to zero.” You’ve solved 3Sum before. You know sorting plus two pointers. But now you need to explain why you sort, handle duplicate values at two different levels, and justify every pointer movement while someone watches you code it live.

This walkthrough covers the complete arc: from brute force to the optimal O(n²) approach, with duplicate-skipping logic explained at each level, edge cases called out, and a model of what a polished interview performance sounds like.

---

The Problem

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 solution set must not contain duplicate triplets. (LeetCode #15)

Example

Input nums = [-1, 0, 1, 2, -1, -4]

Output [[-1, -1, 2], [-1, 0, 1]]

After sorting, the array becomes [-4, -1, -1, 0, 1, 2]. Fixing -1 at index 1 and using two pointers on the rest finds [-1, 0, 1] and [-1, -1, 2]. The triplet [-1, 0, 1] appears only once in the output even though -1 appears twice in the input. The problem requires unique triplets, which is the detail that makes this problem significantly harder than it first appears.

Already comfortable with the solution? Practice it in a mock interview →

---

What Interviewers Are Actually Testing

3Sum is a deliberate complexity step up from Two Sum. Interviewers use it to probe whether you can manage multiple moving parts: sorting as a preprocessing step, a fixed outer pointer, an inner two-pointer scan, and duplicate suppression at two separate levels.

Skill	What Interviewers Observe
Problem decomposition	Do you reduce 3Sum to a sorted array + Two Sum II pattern?
Sorting intuition	Do you recognize sorting as a prerequisite that enables deduplication and two pointers?
Two-pointer mechanics	Can you correctly advance left and right based on sum comparisons?
Duplicate suppression	Do you skip duplicate values for both the outer i pointer and inner left/right pointers?
Edge case handling	Do you handle arrays shorter than 3, all-zero arrays, and no-solution cases?
Complexity awareness	Can you justify why O(n²) is optimal for this problem?

---

Step 1: Clarifying Questions

Smart clarifying questions before coding demonstrate that you think structurally about a problem rather than diving in immediately. Here are the most valuable ones for 3Sum:

1. Can the array contain duplicate values? Yes, and this is the crux of the problem. The input [-1, -1, 0, 1] can form the triplet [-1, 0, 1], but it should only appear once in the output. Knowing duplicates exist upfront means you design your solution with deduplication in mind from the start.

2. Must I return the actual triplets, or just a count? The problem asks for all unique triplets as lists. Confirming this matters because returning a count would be a different and simpler problem.

3. Can the same element be used more than once in a triplet? No. The indices must be distinct (i != j != k). This means [0, 0, 0] is valid only if three separate zeros exist in the array, not by reusing a single zero.

4. What should I return if no valid triplet exists? Return an empty list. Confirming this prevents ambiguity about error handling.

5. Are there constraints on array length that suggest the expected time complexity? LeetCode allows up to 3,000 elements. An O(n³) brute force would mean 27 billion operations, clearly unacceptable. O(n²) is the target, and confirming the scale helps you justify the sorting + two-pointer approach.

---

Step 2: A First (Non-Optimal) Idea

The most natural starting point is a triple nested loop: try every combination of three indices and check if their values sum to zero.

def threeSum(nums):
    result = set()
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                if nums[i] + nums[j] + nums[k] == 0:
                    triplet = tuple(sorted([nums[i], nums[j], nums[k]]))
                    result.add(triplet)
    return [list(t) for t in result, "medium"]

This is O(n³) in time and uses a set to handle deduplication. Correct in output, but far too slow. For 3,000 elements, this is 4.5 billion iterations.

Approach	Time	Space
Brute force (triple loop + set)	O(n³)	O(n) for dedup set
Hash-based (fix one, hash lookup)	O(n²)	O(n)
Sort + two pointers	O(n²)	O(1) extra

Present this clearly, then pivot: “O(n³) is a correct starting point but doesn’t scale. If I sort the array first, I can use two pointers for the inner search and skip duplicates in O(1), getting to O(n²) overall.”

---

Step 3: The Key Insight

Sort the array first. Then for each element nums[i], the problem reduces to “find two numbers in the rest of the array that sum to -nums[i].” That’s Two Sum on a sorted array, solvable in O(n) with two pointers.

Here’s the chain of reasoning that unlocks the optimal solution:

Step one: Sort the array. Sorting costs O(n log n), negligible compared to the O(n²) scan that follows. More importantly, sorting enables two things: it makes two-pointer scanning possible, and it groups duplicate values together so they’re easy to skip.

Step two: Fix one element at a time with an outer loop. For each index i, your problem reduces to: “find two numbers in the remaining array that sum to -nums[i].” That’s exactly Two Sum on a sorted array, solvable in O(n) with two pointers moving inward from both ends.

Step three: Skip duplicates deliberately at both levels. After processing index i, if nums[i+1] == nums[i], skip it. It would produce the same triplets. Similarly, after finding a valid triplet with left and right, advance both pointers past any values equal to nums[left] and nums[right] before continuing.

This three-part insight (sort, fix one, two-pointer scan, skip duplicates at every level) is the complete 3Sum explanation. The code follows directly from it.

---

Step 4: Optimal Strategy

Here’s the full algorithm, step by step:

1. Sort nums in ascending order.
2. If len(nums) < 3, return an empty list immediately.
3. Initialize an empty list result to collect valid triplets.
4. Iterate i from 0 to len(nums) - 3 (inclusive):
   • Early termination: If nums[i] > 0, break. A sorted array means no three elements from here onward can sum to zero.
   • Skip outer duplicates: If i > 0 and nums[i] == nums[i - 1], skip this iteration to avoid duplicate triplets.
   • Set left = i + 1 and right = len(nums) - 1.
5. While left < right:
   • Compute total = nums[i] + nums[left] + nums[right].
   • If total == 0: append [nums[i], nums[left], nums[right]] to result. Then advance left forward past duplicates and right backward past duplicates. Then increment left and decrement right.
   • If total < 0: increment left to increase the sum.
   • If total > 0: decrement right to decrease the sum.
6. Return result.

---

Python Implementation

def threeSum(nums: list[int]) -> list[list[int]]:
    nums.sort()  # Sorting enables two pointers and easy duplicate skipping
    result = [, "medium"]

    for i in range(len(nums) - 2):
        # Early exit: smallest remaining value is positive, no valid triplet possible
        if nums[i] > 0:
            break

        # Skip duplicate values for the outer pointer
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        left, right = i + 1, len(nums) - 1

        while left < right:
            total = nums[i] + nums[left] + nums[right, "medium"]

            if total == 0:
                result.append([nums[i], nums[left], nums[right]])

                # Skip duplicates for the inner left pointer
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                # Skip duplicates for the inner right pointer
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1

                # Move both pointers inward to search for more triplets
                left += 1
                right -= 1

            elif total < 0:
                left += 1   # Sum too small, increase left to raise the total
            else:
                right -= 1  # Sum too large, decrease right to lower the total

    return result

Key implementation notes worth calling out in an interview:

• range(len(nums) - 2) ensures left and right always have at least two elements to work with.
• The if nums[i] > 0: break early termination is a meaningful optimization. Once the fixed element is positive in a sorted array, the two remaining elements (which are equal or larger) can never sum to zero with it.
• Duplicate skipping happens at two distinct levels: outer (i pointer) and inner (left and right pointers). They use different guard conditions. Mixing them up is one of the most common bugs.
• After skipping inner duplicates, both left and right are incremented/decremented one final time to move past the matched values entirely.

---

Time & Space Complexity

Operation	Complexity
Sorting	O(n log n)
Outer loop × inner two-pointer scan	O(n²)
Overall time	O(n²)
Space (excluding output)	O(1) or O(n) depending on sort

Time: The outer loop runs O(n) times. For each iteration, the two-pointer inner scan runs in O(n). Combined: O(n²), which dominates the O(n log n) sort.

Space: Python’s sort() uses Timsort, which is O(n) auxiliary space. The output list itself can hold up to O(n²) triplets in the worst case, but that’s output space, not algorithmic space. The working space beyond sorting is O(1).

Is O(n²) optimal? Yes. It can be proven that any comparison-based algorithm for 3Sum requires Ω(n²) time in the worst case. Mentioning this shows you’ve thought about the lower bound, not just the upper bound.

---

Common Interview Mistakes

1. Forgetting to sort first. The entire two-pointer approach depends on sorted order. Without sorting, you can’t use directional pointer movement, and duplicate skipping becomes far more complex. Always sort before anything else.

2. Skipping outer duplicates with the wrong condition. The guard if i > 0 and nums[i] == nums[i - 1] is correct. Using nums[i] == nums[i + 1] instead would skip a value before processing it, potentially missing valid triplets that start with that value.

3. Forgetting to skip inner duplicates after a match. After appending a valid triplet, if you just do left += 1; right -= 1 without skipping duplicates, you’ll append the same triplet multiple times. The inner while loops are not optional.

4. Moving only one pointer after a match. After finding a triplet, both left and right must move. Moving only one leaves the other pointer in a state that causes an infinite loop or missed results.

5. Not handling the early termination. Omitting if nums[i] > 0: break produces a correct but slower solution. The two-pointer scan runs uselessly for all-positive suffixes. Interviewers may ask about optimizations; having this ready is a good signal.

6. Confusing the output requirement. The problem asks for the actual triplet values [a, b, c], not indices. Returning indices (like Two Sum) is a common slip when candidates are moving quickly.

7. Not narrating the duplicate-handling logic. The deduplication is the hardest part of this problem to reason about. Candidates who code it silently, even if correctly, miss an opportunity to demonstrate they actually understand why it works.

---

What a Strong Candidate Sounds Like

“3Sum reduces to Two Sum once I fix one element. Here’s my plan: sort the array first, that costs O(n log n) but enables both two pointers and easy duplicate skipping. Then I iterate with an outer pointer i, and for each i, run a two-pointer scan on the rest to find pairs that sum to -nums[i].

The tricky part is deduplication. After sorting, I skip the outer pointer forward if nums[i] == nums[i-1], because the same value would produce the same triplets. Inside the scan, after finding a valid triplet, I skip both the left and right pointers past any equal values before moving on.

One small optimization: if nums[i] > 0, I break early. In a sorted array, all remaining elements are at least as large, so no valid triplet can sum to zero from here. Overall: O(n²) time, O(1) extra space. Let me code it up and trace through the example.”

---

Example Interview Dialogue

Interviewer: Given an array, find all unique triplets that sum to zero.

Candidate: A few quick questions: can the input have duplicates? And I should return the triplets themselves, not indices?

Interviewer: Yes, duplicates are possible. Return the triplets.

Candidate: Got it. Brute force is O(n³), too slow. My approach: sort the array, then for each element nums[i], use two pointers left and right to find pairs summing to -nums[i]. Sorting makes two pointers work and groups duplicates so I can skip them.

Interviewer: How do you handle duplicates?

Candidate: At two levels. For the outer pointer, after sorting, if nums[i] == nums[i-1], I skip. Same first element means same triplets. For the inner pointers, after recording a valid triplet, I advance both left and right past any repeated values before continuing the scan.

Interviewer: What’s your time complexity?

Candidate: O(n²). The outer loop is O(n), and the two-pointer scan inside is O(n). Sorting is O(n log n), which is dominated. Space is O(1) for the algorithm itself, not counting the output.

Interviewer: How would you extend this to 4Sum?

Candidate: Add another outer loop fixing a second element, making it O(n³) overall. For each pair (i, j), run the same two-pointer scan looking for pairs summing to target - nums[i] - nums[j]. Duplicate skipping applies at three levels now, for i, j, and the inner pointers. The pattern generalizes: k-Sum can be solved with (k-2) nested loops plus one two-pointer pass.

---

Related Problems

3Sum sits at the center of a rich problem family built on sorting and multi-pointer techniques:

• Two Sum (LeetCode #1). The foundation. 3Sum reduces to this after fixing one element.
• Two Sum II (Sorted Array) (LeetCode #167). Two-pointer Two Sum, the exact inner loop used in 3Sum.
• 4Sum (LeetCode #18). Direct extension with one more outer loop and the same two-pointer core.
• 3Sum Closest (LeetCode #16). Same structure as 3Sum but tracks the triplet closest to a target instead of exactly equal.
• 3Sum Smaller (LeetCode #259). Count triplets summing to less than a target, same sort + two-pointer pattern with a different termination condition.

The jump from 3Sum to 4Sum is one of the most common interview escalations. If you can explain the pattern generalization clearly (“each additional element adds one outer loop”), you signal real understanding rather than memorization.

---

Practice This in a Mock Interview

Reading through this gives you the mental model: sort, fix, scan, deduplicate. But 3Sum is one of those problems where candidates consistently understand the solution and still write buggy code under pressure. The duplicate-skipping conditions have just enough subtlety that off-by-one errors and wrong guard conditions creep in the moment someone is watching the clock.

The only reliable way to build the muscle memory for clean, bug-free 3Sum code is to practice it out loud, under timed conditions, with follow-up questions. Knowing the answer and performing it fluently are two genuinely different skills.

Start a mock interview for 3Sum on Intervu.

---

Related Problems to Practice

• Two Sum — The foundational hash map complement pattern.
• Container With Most Water — Two-pointer technique on unsorted arrays.
• Sort Colors — Three-pointer partitioning on arrays.

Further reading:

• How to Prepare for a Coding Interview in 2026, the complete roadmap and study plans
• Why LeetCode alone isn’t enough, and what to practice instead
• Practice any LeetCode problem as a live mock interview
• The Grind 75 Pathway, a structured study plan with AI practice links
• Browse all walkthroughs on GitHub, condensed solutions with code