3Sum

Difficulty: Medium Source: NeetCode

Problem

Given an integer array nums, return all the 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.

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

Example 2: Input: nums = [0,1,1] Output: []

Example 3: Input: nums = [0,0,0] Output: [[0,0,0]]

Constraints:

• 3 <= nums.length <= 3000
• -10^5 <= nums[i] <= 10^5

Prerequisites

Before attempting this problem, you should be comfortable with:

• Two Sum II — two-pointer search in a sorted array for a specific target
• Sorting — why sorting enables efficient duplicate skipping
• Two Pointers — applying two pointers as a subroutine inside a loop

1. Brute Force

Intuition

Try every combination of three distinct indices. If they sum to zero, add the sorted triplet to a set to deduplicate. Convert the set to a list at the end. It’s correct but painfully slow for large inputs — O(n³) from three nested loops.

Algorithm

1. Initialize result as a set.
2. For every trio of indices i < j < k:
   • If nums[i] + nums[j] + nums[k] == 0, add tuple(sorted([nums[i], nums[j], nums[k]])) to result.
3. Return [list(t) for t in result].

Solution

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:
                    result.add(tuple(sorted([nums[i], nums[j], nums[k]])))
    return [list(t) for t in result]


print(threeSum([-1, 0, 1, 2, -1, -4]))  # [[-1, -1, 2], [-1, 0, 1]]
print(threeSum([0, 1, 1]))               # []
print(threeSum([0, 0, 0]))               # [[0, 0, 0]]

Complexity

• Time: O(n³)
• Space: O(k) where k is the number of unique triplets

2. Sort + Two Pointers

Intuition

Sort the array first. Then fix one element nums[i] with an outer loop and reduce the problem to Two Sum II on the remaining subarray: find two numbers in nums[i+1 .. n-1] that sum to -nums[i]. Use two pointers (left = i + 1, right = n - 1) for that inner search.

The key insight for deduplication: because the array is sorted, duplicates are adjacent. After placing a triplet, skip over any repeated values for both the outer index and the inner pointers — that way each unique triplet is found exactly once.

Algorithm

1. Sort nums.
2. For i from 0 to n - 3:
   • Skip if nums[i] == nums[i - 1] and i > 0 (duplicate outer element).
   • Set left = i + 1, right = n - 1, target = -nums[i].
   • While left < right:
     • If nums[left] + nums[right] == target: record triplet, advance left and retreat right, then skip duplicates on both sides.
     • If sum < target: increment left.
     • If sum > target: decrement right.
3. Return result.

Solution

def threeSum(nums):
    nums.sort()
    result = []
    n = len(nums)

    for i in range(n - 2):
        # Skip duplicate values for the fixed element
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        left, right = i + 1, n - 1
        target = -nums[i]

        while left < right:
            total = nums[left] + nums[right]
            if total == target:
                result.append([nums[i], nums[left], nums[right]])
                left += 1
                right -= 1
                # Skip duplicates for left and right pointers
                while left < right and nums[left] == nums[left - 1]:
                    left += 1
                while left < right and nums[right] == nums[right + 1]:
                    right -= 1
            elif total < target:
                left += 1
            else:
                right -= 1

    return result


print(threeSum([-1, 0, 1, 2, -1, -4]))  # [[-1, -1, 2], [-1, 0, 1]]
print(threeSum([0, 1, 1]))               # []
print(threeSum([0, 0, 0]))               # [[0, 0, 0]]

Complexity

• Time: O(n²)
• Space: O(1) extra (output list not counted)

Common Pitfalls

Skipping duplicates in the wrong place. The outer duplicate skip (i > 0 and nums[i] == nums[i-1]) must use i > 0 as a guard, otherwise you’d skip index 0 altogether. The inner duplicate skips happen after recording a triplet, not before.

Early termination optimization. If nums[i] > 0 after sorting, all remaining elements are also positive, so no triplet can sum to zero. Adding if nums[i] > 0: break speeds things up in practice.

Modifying the input. nums.sort() sorts in-place. If the caller cares about the original order, sort a copy. In a typical interview, in-place sorting is fine.