3Sum#

Given an array of integers, find every unique triplet that sums to zero. The three numbers must sit at distinct indices, and the returned set of triplets must not contain duplicates. Return the triplets in any order.

Example#

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

Brute force#

Check every combination of three indices with three nested loops and collect those that sum to zero, deduplicating at the end. This is far too slow for large inputs.

• Time: O(n^3).
• Space: O(1) beyond the output.

Optimal approach#

Sort the array first. Fix each number as the first element of a triplet, then run a two-pointer search over the rest of the array for two values that complete the sum to zero. Sorting lets you move pointers based on whether the current sum is too small or too large, and it makes duplicates adjacent so you can skip them cleanly.

Python solution#

 1def three_sum(nums):
 2    nums.sort()
 3    result = []
 4    n = len(nums)
 5    for i in range(n - 2):
 6        if i > 0 and nums[i] == nums[i - 1]:
 7            continue
 8        left, right = i + 1, n - 1
 9        while left < right:
10            total = nums[i] + nums[left] + nums[right]
11            if total < 0:
12                left += 1
13            elif total > 0:
14                right -= 1
15            else:
16                result.append([nums[i], nums[left], nums[right]])
17                left += 1
18                right -= 1
19                while left < right and nums[left] == nums[left - 1]:
20                    left += 1
21                while left < right and nums[right] == nums[right + 1]:
22                    right -= 1
23    return result

Complexity#

• Time: O(n^2), the outer loop times the linear two-pointer scan.
• Space: O(1) extra, ignoring the output and sort space.

This problem layers the two-pointer technique on top of sorting. Keep practicing with the 60-day challenge.