Language Selection
Choose your preferred programming language
Three Sum (Triplets that Sum to Zero)
Problem Statement
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.
Constraints:
3 <= nums.length <= 3000-10^5 <= nums[i] <= 10^5
Examples:
Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Example 2:
Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.
Example 3:
Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.
Approach 1: Two Pointers (Optimal)
Algorithm:
- Sort the array
- Fix the first element and use two pointers for the remaining two elements
- Skip duplicates to avoid duplicate triplets
- Move pointers based on the current sum
Time Complexity: O(n²)
Space Complexity: O(1)
Python:
def threeSum(nums):
"""
Find all unique triplets that sum to zero using two pointers
Time: O(n²)
Space: O(1)
"""
nums.sort()
result = []
for i in range(len(nums) - 2):
# Skip duplicates for the first element
if i > 0 and nums[i] == nums[i - 1]:
continue
left, right = i + 1, len(nums) - 1
while left < right:
current_sum = nums[i] + nums[left] + nums[right]
if current_sum == 0:
result.append([nums[i], nums[left], nums[right]])
# Skip duplicates for the second element
while left < right and nums[left] == nums[left + 1]:
left += 1
# Skip duplicates for the third element
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
elif current_sum < 0:
left += 1
else:
right -= 1
return result
Java:
class Solution {
/**
* Find all unique triplets that sum to zero using two pointers
* Time: O(n²)
* Space: O(1)
*/
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < nums.length - 2; i++) {
// Skip duplicates for the first element
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
int currentSum = nums[i] + nums[left] + nums[right];
if (currentSum == 0) {
result.add(Arrays.asList(nums[i], nums[left], nums[right]));
// Skip duplicates for the second element
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
// Skip duplicates for the third element
while (left < right && nums[right] == nums[right - 1]) {
right--;
}
left++;
right--;
} else if (currentSum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}
}
Go:
// threeSum - Find all unique triplets that sum to zero using two pointers
// Time: O(n²)
// Space: O(1)
func threeSum(nums []int) [][]int {
sort.Ints(nums)
var result [][]int
for i := 0; i < len(nums)-2; i++ {
// Skip duplicates for the first element
if i > 0 && nums[i] == nums[i-1] {
continue
}
left, right := i+1, len(nums)-1
for left < right {
currentSum := nums[i] + nums[left] + nums[right]
if currentSum == 0 {
result = append(result, []int{nums[i], nums[left], nums[right]})
// Skip duplicates for the second element
for left < right && nums[left] == nums[left+1] {
left++
}
// Skip duplicates for the third element
for left < right && nums[right] == nums[right-1] {
right--
}
left++
right--
} else if currentSum < 0 {
left++
} else {
right--
}
}
}
return result
}
JavaScript:
/**
* Find all unique triplets that sum to zero using two pointers
* Time: O(n²)
* Space: O(1)
*/
function threeSum(nums) {
nums.sort((a, b) => a - b);
const result = [];
for (let i = 0; i < nums.length - 2; i++) {
// Skip duplicates for the first element
if (i > 0 && nums[i] === nums[i - 1]) {
continue;
}
let left = i + 1;
let right = nums.length - 1;
while (left < right) {
const currentSum = nums[i] + nums[left] + nums[right];
if (currentSum === 0) {
result.push([nums[i], nums[left], nums[right]]);
// Skip duplicates for the second element
while (left < right && nums[left] === nums[left + 1]) {
left++;
}
// Skip duplicates for the third element
while (left < right && nums[right] === nums[right - 1]) {
right--;
}
left++;
right--;
} else if (currentSum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}
C#:
public class Solution {
/// <summary>
/// Find all unique triplets that sum to zero using two pointers
/// Time: O(n²)
/// Space: O(1)
/// </summary>
public IList<IList<int>> ThreeSum(int[] nums) {
Array.Sort(nums);
IList<IList<int>> result = new List<IList<int>>();
for (int i = 0; i < nums.Length - 2; i++) {
// Skip duplicates for the first element
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.Length - 1;
while (left < right) {
int currentSum = nums[i] + nums[left] + nums[right];
if (currentSum == 0) {
result.Add(new List<int> { nums[i], nums[left], nums[right] });
// Skip duplicates for the second element
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
// Skip duplicates for the third element
while (left < right && nums[right] == nums[right - 1]) {
right--;
}
left++;
right--;
} else if (currentSum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}
}
C++:
#include <algorithm>
#include <vector>
using namespace std;
class Solution {
public:
// Find all unique triplets that sum to zero using two pointers
// Time: O(n²)
// Space: O(1) extra (besides the output and the sort)
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> result;
int n = static_cast<int>(nums.size());
for (int i = 0; i < n - 2; i++) {
// Skip duplicates for the first element
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = n - 1;
while (left < right) {
int currentSum = nums[i] + nums[left] + nums[right];
if (currentSum == 0) {
result.push_back({nums[i], nums[left], nums[right]});
// Skip duplicates for the second element
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
// Skip duplicates for the third element
while (left < right && nums[right] == nums[right - 1]) {
right--;
}
left++;
right--;
} else if (currentSum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}
};
Approach 2: Hash Set
Algorithm:
- Sort the array
- Fix the first element and use a hash set to find the third element
- Skip duplicates to avoid duplicate triplets
Time Complexity: O(n²)
Space Complexity: O(n)
Python:
def threeSum(nums):
"""
Find all unique triplets that sum to zero using hash set
Time: O(n²)
Space: O(n)
"""
nums.sort()
result = []
for i in range(len(nums) - 2):
# Skip duplicates for the first element
if i > 0 and nums[i] == nums[i - 1]:
continue
seen = set()
target = -nums[i]
j = i + 1
while j < len(nums):
complement = target - nums[j]
if complement in seen:
result.append([nums[i], complement, nums[j]])
# Skip duplicates for the second element
while j + 1 < len(nums) and nums[j] == nums[j + 1]:
j += 1
seen.add(nums[j])
j += 1
return result
Java:
class Solution {
/**
* Find all unique triplets that sum to zero using hash set
* Time: O(n²)
* Space: O(n)
*/
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < nums.length - 2; i++) {
// Skip duplicates for the first element
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
Set<Integer> seen = new HashSet<>();
int target = -nums[i];
for (int j = i + 1; j < nums.length; j++) {
int complement = target - nums[j];
if (seen.contains(complement)) {
result.add(Arrays.asList(nums[i], complement, nums[j]));
// Skip duplicates for the second element
while (j + 1 < nums.length && nums[j] == nums[j + 1]) {
j++;
}
}
seen.add(nums[j]);
}
}
return result;
}
}
Go:
// threeSum - Find all unique triplets that sum to zero using hash set
// Time: O(n²)
// Space: O(n)
func threeSum(nums []int) [][]int {
sort.Ints(nums)
var result [][]int
for i := 0; i < len(nums)-2; i++ {
// Skip duplicates for the first element
if i > 0 && nums[i] == nums[i-1] {
continue
}
seen := make(map[int]bool)
target := -nums[i]
for j := i + 1; j < len(nums); j++ {
complement := target - nums[j]
if seen[complement] {
result = append(result, []int{nums[i], complement, nums[j]})
// Skip duplicates for the second element
for j+1 < len(nums) && nums[j] == nums[j+1] {
j++
}
}
seen[nums[j]] = true
}
}
return result
}
JavaScript:
/**
* Find all unique triplets that sum to zero using hash set
* Time: O(n²)
* Space: O(n)
*/
function threeSum(nums) {
nums.sort((a, b) => a - b);
const result = [];
for (let i = 0; i < nums.length - 2; i++) {
// Skip duplicates for the first element
if (i > 0 && nums[i] === nums[i - 1]) {
continue;
}
const seen = new Set();
const target = -nums[i];
for (let j = i + 1; j < nums.length; j++) {
const complement = target - nums[j];
if (seen.has(complement)) {
result.push([nums[i], complement, nums[j]]);
// Skip duplicates for the second element
while (j + 1 < nums.length && nums[j] === nums[j + 1]) {
j++;
}
}
seen.add(nums[j]);
}
}
return result;
}
C#:
public class Solution {
/// <summary>
/// Find all unique triplets that sum to zero using hash set
/// Time: O(n²)
/// Space: O(n)
/// </summary>
public IList<IList<int>> ThreeSum(int[] nums) {
Array.Sort(nums);
IList<IList<int>> result = new List<IList<int>>();
for (int i = 0; i < nums.Length - 2; i++) {
// Skip duplicates for the first element
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
HashSet<int> seen = new HashSet<int>();
int target = -nums[i];
for (int j = i + 1; j < nums.Length; j++) {
int complement = target - nums[j];
if (seen.Contains(complement)) {
result.Add(new List<int> { nums[i], complement, nums[j] });
// Skip duplicates for the second element
while (j + 1 < nums.Length && nums[j] == nums[j + 1]) {
j++;
}
}
seen.Add(nums[j]);
}
}
return result;
}
}
C++:
#include <algorithm>
#include <unordered_set>
#include <vector>
using namespace std;
class Solution {
public:
// Find all unique triplets that sum to zero using hash set
// Time: O(n²)
// Space: O(n)
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> result;
int n = static_cast<int>(nums.size());
for (int i = 0; i < n - 2; i++) {
// Skip duplicates for the first element
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
unordered_set<int> seen;
int target = -nums[i];
for (int j = i + 1; j < n; j++) {
int complement = target - nums[j];
if (seen.count(complement)) {
result.push_back({nums[i], complement, nums[j]});
// Skip duplicates for the second element
while (j + 1 < n && nums[j] == nums[j + 1]) {
j++;
}
}
seen.insert(nums[j]);
}
}
return result;
}
};
Approach 3: Brute Force
Algorithm:
- Sort a copy of the array
- Try every triplet with three nested loops and keep the ones that sum to zero
- Skip equal values at each of the three positions, so each unique triplet is produced exactly once
Time Complexity: O(n³)
Space Complexity: O(n) for the sorted copy, plus the output
Python:
def threeSum(nums):
"""
Find all unique triplets that sum to zero using brute force
Time: O(n³)
Space: O(n) for the sorted copy, plus the output
"""
result = []
s = sorted(nums)
n = len(s)
for i in range(n - 2):
# Skip equal values for the first element
if i > 0 and s[i] == s[i - 1]:
continue
for j in range(i + 1, n - 1):
# Skip equal values for the second element
if j > i + 1 and s[j] == s[j - 1]:
continue
for k in range(j + 1, n):
# Skip equal values for the third element
if k > j + 1 and s[k] == s[k - 1]:
continue
# Each unique triplet is reached exactly once, so no duplicate check is needed
if s[i] + s[j] + s[k] == 0:
result.append([s[i], s[j], s[k]])
return result
Java:
class Solution {
/**
* Find all unique triplets that sum to zero using brute force
* Time: O(n³)
* Space: O(n) for the sorted copy, plus the output
*/
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
int[] s = nums.clone();
Arrays.sort(s);
int n = s.length;
for (int i = 0; i < n - 2; i++) {
// Skip equal values for the first element
if (i > 0 && s[i] == s[i - 1]) continue;
for (int j = i + 1; j < n - 1; j++) {
// Skip equal values for the second element
if (j > i + 1 && s[j] == s[j - 1]) continue;
for (int k = j + 1; k < n; k++) {
// Skip equal values for the third element
if (k > j + 1 && s[k] == s[k - 1]) continue;
// Each unique triplet is reached exactly once, so no duplicate check is needed
if (s[i] + s[j] + s[k] == 0) {
result.add(Arrays.asList(s[i], s[j], s[k]));
}
}
}
}
return result;
}
}
Go:
// threeSum - Find all unique triplets that sum to zero using brute force
// Time: O(n³)
// Space: O(n) for the sorted copy, plus the output
func threeSum(nums []int) [][]int {
s := append([]int(nil), nums...)
sort.Ints(s)
n := len(s)
var result [][]int
for i := 0; i < n-2; i++ {
// Skip equal values for the first element
if i > 0 && s[i] == s[i-1] {
continue
}
for j := i + 1; j < n-1; j++ {
// Skip equal values for the second element
if j > i+1 && s[j] == s[j-1] {
continue
}
for k := j + 1; k < n; k++ {
// Skip equal values for the third element
if k > j+1 && s[k] == s[k-1] {
continue
}
// Each unique triplet is reached exactly once, so no duplicate check is needed
if s[i]+s[j]+s[k] == 0 {
result = append(result, []int{s[i], s[j], s[k]})
}
}
}
}
return result
}
JavaScript:
/**
* Find all unique triplets that sum to zero using brute force
* Time: O(n³)
* Space: O(n) for the sorted copy, plus the output
*/
function threeSum(nums) {
const result = [];
const s = [...nums].sort((a, b) => a - b);
const n = s.length;
for (let i = 0; i < n - 2; i++) {
// Skip equal values for the first element
if (i > 0 && s[i] === s[i - 1]) continue;
for (let j = i + 1; j < n - 1; j++) {
// Skip equal values for the second element
if (j > i + 1 && s[j] === s[j - 1]) continue;
for (let k = j + 1; k < n; k++) {
// Skip equal values for the third element
if (k > j + 1 && s[k] === s[k - 1]) continue;
// Each unique triplet is reached exactly once, so no duplicate check is needed
if (s[i] + s[j] + s[k] === 0) {
result.push([s[i], s[j], s[k]]);
}
}
}
}
return result;
}
C#:
public class Solution {
/// <summary>
/// Find all unique triplets that sum to zero using brute force
/// Time: O(n³)
/// Space: O(n) for the sorted copy, plus the output
/// </summary>
public IList<IList<int>> ThreeSum(int[] nums) {
IList<IList<int>> result = new List<IList<int>>();
int[] s = (int[])nums.Clone();
Array.Sort(s);
int n = s.Length;
for (int i = 0; i < n - 2; i++) {
// Skip equal values for the first element
if (i > 0 && s[i] == s[i - 1]) continue;
for (int j = i + 1; j < n - 1; j++) {
// Skip equal values for the second element
if (j > i + 1 && s[j] == s[j - 1]) continue;
for (int k = j + 1; k < n; k++) {
// Skip equal values for the third element
if (k > j + 1 && s[k] == s[k - 1]) continue;
// Each unique triplet is reached exactly once, so no duplicate check is needed
if (s[i] + s[j] + s[k] == 0) {
result.Add(new List<int> { s[i], s[j], s[k] });
}
}
}
}
return result;
}
}
C++:
#include <algorithm>
#include <vector>
using namespace std;
class Solution {
public:
// Find all unique triplets that sum to zero using brute force
// Time: O(n³)
// Space: O(n) for the sorted copy, plus the output
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
vector<int> sorted(nums);
sort(sorted.begin(), sorted.end());
int n = static_cast<int>(sorted.size());
for (int i = 0; i < n - 2; i++) {
// Skip equal values for the first element
if (i > 0 && sorted[i] == sorted[i - 1]) continue;
for (int j = i + 1; j < n - 1; j++) {
// Skip equal values for the second element
if (j > i + 1 && sorted[j] == sorted[j - 1]) continue;
for (int k = j + 1; k < n; k++) {
// Skip equal values for the third element
if (k > j + 1 && sorted[k] == sorted[k - 1]) continue;
// Each unique triplet is reached exactly once, so no duplicate check is needed
if (sorted[i] + sorted[j] + sorted[k] == 0) {
result.push_back({sorted[i], sorted[j], sorted[k]});
}
}
}
}
return result;
}
};
Key Insights
Sorting is crucial: It allows us to use two pointers and skip duplicates efficiently.
Two Pointers Technique: After fixing one element, we can use two pointers to find the other two elements in O(n) time.
Duplicate Handling: We must skip duplicates at each level to avoid duplicate triplets in the result.
Early Termination (optional): After sorting, if the first element is positive you could break early, since all remaining elements are also positive. The implementations above don’t include this optimization.
Edge Cases
- All zeros:
[0,0,0]→ result is[[0,0,0]] - No solution:
[1,2,3]→ result is[] - All negative:
[-1,-2,-3]→ result is[] - Duplicates:
[-1,-1,0,1,1]→ result is[[-1,0,1]]
Test Cases
# Test case 1: Mixed positive and negative
assert threeSum([-1,0,1,2,-1,-4]) == [[-1,-1,2],[-1,0,1]]
# Test case 2: No solution
assert threeSum([0,1,1]) == []
# Test case 3: All zeros
assert threeSum([0,0,0]) == [[0,0,0]]
# Test case 4: Single solution
assert threeSum([-1,0,1]) == [[-1,0,1]]
# Test case 5: Multiple duplicates
assert threeSum([-2,0,1,1,2]) == [[-2,0,2],[-2,1,1]]
Follow-up Questions
Four Sum: Find all unique quadruplets that sum to a target value.
Three Sum Closest: Find three integers whose sum is closest to a target.
Three Sum Smaller: Count the number of triplets with sum smaller than target.
K Sum: Generalize to find k elements that sum to target.
Common Mistakes
- Not handling duplicates: Forgetting to skip duplicate elements at each level.
- Incorrect pointer movement: Not moving both pointers when a valid triplet is found.
- Off-by-one errors: Incorrect loop bounds or pointer initialization.
- Not sorting: Trying to solve without sorting first.
Trade-offs
- Two Pointers vs Hash Set: Two pointers is more space-efficient, hash set is easier to understand
- Brute Force: Simple but inefficient for large inputs
- Space vs Time: Hash set uses O(n) space but same time complexity
- Sorting: Required for efficient duplicate handling