3Sum

Problem

Given an integer array nums, return all unique triplets[a, b, c] such that a + b + c = 0. The solution set must not contain duplicate triplets.

Example: nums = [-1, 0, 1, 2, -1, -4] → [[-1, -1, 2], [-1, 0, 1]].

What the interviewer is testing

• Do you decompose the problem to Two Sum in a loop?
• Do you use sort + two pointers rather than a hash set (avoids duplicate handling headaches)?
• Do you correctly skip duplicates at all three levels (i, left, right)?

Approach

Sort the array. Fix one element nums[i]. Now the remaining task is: find two numbers in the (still sorted) subarray that sum to -nums[i]. That's exactly two-sum on a sorted array — two pointers, O(n) per fix.

Optimal solution — O(n²) time, O(1) space (excluding output)

def three_sum(nums):
    nums.sort()
    result = []
    n = len(nums)
    for i in range(n - 2):
        # Skip duplicates for the fixed element
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        # If the smallest possible triplet is already > 0, we can stop
        if nums[i] + nums[i + 1] + nums[i + 2] > 0:
            break
        target = -nums[i]
        left, right = i + 1, n - 1
        while left < right:
            s = nums[left] + nums[right]
            if s == target:
                result.append([nums[i], nums[left], nums[right]])
                # Skip duplicates for left and right
                left += 1
                right -= 1
                while left < right and nums[left]  == nums[left - 1]:  left  += 1
                while left < right and nums[right] == nums[right + 1]: right -= 1
            elif s < target:
                left += 1
            else:
                right -= 1
    return result

Complexity — what to say out loud

"Sort is O(n log n). Then for each of n fixed elements, two pointers work O(n), so total O(n²). Space O(1) beyond the output — we're using in-place sort and constant extra pointers."

The duplicate-handling trap

The interviewer's test case is almost always something like [-1, -1, -1, 0, 1, 2]. Three places to skip duplicates:

• Outer loop — skip i if nums[i] == nums[i-1]
• Inner left — after a hit, skip left forward while equal to previous
• Inner right — after a hit, skip right backward while equal to previous

Miss any of them and you'll return duplicate triplets. Interviewers specifically look for whether you spot this.

Edge cases the interviewer will ask about

• Fewer than 3 elements — return empty.
• All zeros — one triplet [0, 0, 0]. Skips must be robust.
• No triplet sums to zero — return empty.
• Very large positive input — early break saves time when the smallest possible sum is already positive.

Common follow-ups

• "kSum." — Recursion; kSum reduces to (k-1)Sum which reduces to (k-2)Sum, base case is 2Sum with two pointers. Total O(n^(k-1)).
• "3Sum Closest." — Same structure; track the sum with min |sum − target| instead of exact matches.
• "What if the array is very large and we need a streaming approach?" — Discuss trade-offs; this problem is inherently O(n²) in comparisons.

How to verbalize your answer

"I'll sort the array. Then for each element I fix, the remaining problem is Two Sum on a sorted subarray — two pointers, O(n). Total O(n²). The tricky part is skipping duplicates at all three positions: the fixed element, the left pointer after a hit, and the right pointer after a hit. Space O(1) beyond output."