technical interviews

Three Sum

Find all unique triplets in an array that sum to zero

Problem

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

Difficultyintermediate

R — READ

R

READ

Question

What makes a valid triplet? What about duplicates?

Focus

Three distinct indices, sum to 0. No duplicate triplets in output (e.g., [0,-1,1] and [-1,0,1] are the same).

What the Interviewer is Evaluating

Do you understand the 'no duplicates' constraint?

Common Mistake

Returning all triplets, even duplicates, or misunderstanding the duplicate requirement.

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

Note: [-1, 0, 1] is one triplet. [-1, -1, 2] is another. [1, 0, -1] is the same as [-1, 0, 1].

O — OBSERVE

O

OBSERVE

Question

How can I extend the Two Sum idea?

Focus

Fix one element, then find two others that sum to the negative of that element. Sort the array to avoid duplicates and enable two-pointer approach.

What the Interviewer is Evaluating

Can you connect this to Two Sum? Do you see why sorting helps?

Common Mistake

Trying all triplets (O(n³)) without recognizing the two-pointer pattern.

Example: [-1, 0, 1, 2, -1, -4]
Sorted: [-4, -1, -1, 0, 1, 2]
Fix -4: find two numbers that sum to 4. None exist.
Fix -1 (first): find two numbers that sum to 1 → [0, 1]. Result: [-1, 0, 1]
Fix -1 (second): skip (duplicate) or find again carefully to avoid duplicate results
Fix 0: find two numbers that sum to 0 → [-1, 1]. But wait, we'd recount.

P — PSEUDOCODE

P

PSEUDOCODE

Question

How do I avoid duplicates while finding triplets?

Focus

Sort array. For each element, fix it and use two pointers on the rest. Skip duplicates of the fixed element.

What the Interviewer is Evaluating

Clear handling of duplicates in pseudocode.

Common Mistake

Pseudocode that doesn't explain duplicate-skipping logic.

1. Sort the array
2. For each index i (fixed element):
   a. If i > 0 and nums[i] == nums[i-1], skip (duplicate)
   b. Use two pointers (left = i+1, right = len-1)
   c. While left < right:
      • sum = nums[i] + nums[left] + nums[right]
      • If sum == 0, add to result, move both pointers
      • If sum < 0, move left right (need larger sum)
      • If sum > 0, move right left (need smaller sum)
      • Skip duplicates at left and right pointers
3. Return result

I — IMPLEMENT

I

IMPLEMENT

Question

How do I code this without duplicate triplets?

Focus

Sort first. Handle duplicate skipping carefully at all three positions.

What the Interviewer is Evaluating

Correct duplicate-avoidance logic.

Common Mistake

Forgetting to skip duplicates, especially at the left/right pointers.

def threeSum(nums):
    """
    Find all unique triplets that sum to zero.
    
    Args:
        nums: List of integers
    
    Returns:
        List of lists, each triplet summing to 0
    """
    nums.sort()
    result = []
    
    for i in range(len(nums) - 2):
        # Skip duplicate fixed elements
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        
        # If smallest remaining sum is positive, no solution
        if nums[i] > 0:
            break
        
        # Two pointers on the rest
        left, right = i + 1, len(nums) - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total == 0:
                result.append([nums[i], nums[left], nums[right]])
                
                # Skip duplicates on left
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                # Skip duplicates on right
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                
                left += 1
                right -= 1
            elif total < 0:
                left += 1
            else:
                right -= 1
    
    return result

T — TEST

T

TEST

Question

Does my code work on all cases?

Focus

Test: normal case, no triplets, duplicates, all zeros, mixed positive/negative.

What the Interviewer is Evaluating

Correctness and duplicate handling.

Common Mistake

Only testing when triplets exist.

Test 1: [-1,0,1,2,-1,-4] → [[-1,-1,2],[-1,0,1]] ✓
Test 2: [0,0,0,0] → [[0,0,0]] ✓
Test 3: [-2,0,1,1,2] → [[-2,0,2],[-2,1,1]] ✓
Test 4: [1,2,3] → [] (no triplet sums to 0) ✓
Test 5: [-1,-1,-1,2] → [[-1,-1,2]] (-1 + -1 + 2 = 0) ✓

A — ANALYZE

A

ANALYZE

Question

What's the complexity?

Focus

Sorting is O(n log n). For each of n elements, two-pointer scan is O(n). Total: O(n²).

What the Interviewer is Evaluating

Correct complexity breakdown.

Common Mistake

Claiming O(n) or not accounting for sorting vs. loop.

TIME O(n²)
SPACE O(n)

Why: Sorting is O(n log n). The nested loops (fixed element + two pointers) are O(n²). The overall dominant term is O(n²).

Space: Python's sorted() uses Timsort, which requires O(n) auxiliary space. The two-pointer scan itself uses O(1) extra space (just pointers and variables). We don't count output space.

Brute force: Checking all triplets is O(n³). Two-pointer brings it down to O(n²).