Triplet Sum
Given an integer array nums, return all the 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. The order of the triplets, and the order of numbers within each triplet, does not matter.
Example 1
Input: nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]
Explanation: These are the only two combinations of three numbers
that sum to 0. Note that [-1, 2, -1] is the same triplet as
[-1, -1, 2] and is not repeated in the output.
Example 2
Input: nums = [0, 1, 1]
Output: []
Explanation: No triplet sums to 0.
Constraints
3 <= nums.length <= 3000-10^5 <= nums[i] <= 10^5
Sort the array first. Then fix one element nums[i] at a time and
use two pointers (left = i + 1, right = len(nums) - 1) to search
the remaining sorted sub-array for a pair that sums to -nums[i] —
this reduces "find a triplet summing to zero" to the same converging
two-pointer search used in the pair-sum problem, run once per fixed
index. To avoid duplicate triplets in the output, skip over repeated
values for i, and after finding a valid pair, skip over repeated
values for both left and right before continuing.
A brute-force triple-nested loop would take O(n^3) time. Sorting plus
a two-pointer search for each fixed index brings that down to
O(n^2), dominated by the outer loop over i combined with the
linear two-pointer scan inside it.
def triplet_sum(nums: list[int]) -> list[list[int]]:
nums.sort()
n = len(nums)
result = []
for i in range(n - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue # skip duplicate anchors
if nums[i] > 0:
break # smallest element is positive, no triplet can sum to 0
left, right = i + 1, n - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total < 0:
left += 1
elif total > 0:
right -= 1
else:
result.append([nums[i], nums[left], nums[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
return result
Complexity: O(n log n) for the sort plus O(n^2) for the outer loop combined with the inner two-pointer scan, giving O(n^2) overall time. O(1) extra space beyond the output (or O(n)/O(log n) depending on the sort implementation's internal space).
Share this question