Three Sum (Triplets that Sum to Zero)
Coding Challenge
medium
O(n²)
O(1)
arraystwo-pointerssortinghash-table
Language Selection
Choose your preferred programming language
Showing: Python
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;
}
}
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]
for j in range(i + 1, 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])
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;
}
}
Approach 3: Brute Force
Algorithm:
- Generate all possible triplets
- Check if they sum to zero
- Use a set to avoid duplicates
Time Complexity: O(n³)
Space Complexity: O(1)
Python:
def threeSum(nums):
"""
Find all unique triplets that sum to zero using brute force
Time: O(n³)
Space: O(1)
"""
result = []
nums.sort()
for i in range(len(nums) - 2):
for j in range(i + 1, len(nums) - 1):
for k in range(j + 1, len(nums)):
if nums[i] + nums[j] + nums[k] == 0:
triplet = [nums[i], nums[j], nums[k]]
if triplet not in result:
result.append(triplet)
return result
Java:
class Solution {
/**
* Find all unique triplets that sum to zero using brute force
* Time: O(n³)
* Space: O(1)
*/
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
for (int j = i + 1; j < nums.length - 1; j++) {
for (int k = j + 1; k < nums.length; k++) {
if (nums[i] + nums[j] + nums[k] == 0) {
List<Integer> triplet = Arrays.asList(nums[i], nums[j], nums[k]);
if (!result.contains(triplet)) {
result.add(triplet);
}
}
}
}
}
return result;
}
}
Go:
// threeSum - Find all unique triplets that sum to zero using brute force
// 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++ {
for j := i + 1; j < len(nums)-1; j++ {
for k := j + 1; k < len(nums); k++ {
if nums[i]+nums[j]+nums[k] == 0 {
triplet := []int{nums[i], nums[j], nums[k]}
// Check if triplet already exists
exists := false
for _, existing := range result {
if slices.Equal(triplet, existing) {
exists = true
break
}
}
if !exists {
result = append(result, triplet)
}
}
}
}
}
return result
}
JavaScript:
/**
* Find all unique triplets that sum to zero using brute force
* Time: O(n³)
* Space: O(1)
*/
function threeSum(nums) {
const result = [];
nums.sort((a, b) => a - b);
for (let i = 0; i < nums.length - 2; i++) {
for (let j = i + 1; j < nums.length - 1; j++) {
for (let k = j + 1; k < nums.length; k++) {
if (nums[i] + nums[j] + nums[k] === 0) {
const triplet = [nums[i], nums[j], nums[k]];
// Check if triplet already exists
const exists = result.some(existing =>
existing.every((val, idx) => val === triplet[idx])
);
if (!exists) {
result.push(triplet);
}
}
}
}
}
return result;
}
C#:
public class Solution {
/// <summary>
/// Find all unique triplets that sum to zero using brute force
/// Time: O(n³)
/// Space: O(1)
/// </summary>
public IList<IList<int>> ThreeSum(int[] nums) {
IList<IList<int>> result = new List<IList<int>>();
Array.Sort(nums);
for (int i = 0; i < nums.Length - 2; i++) {
for (int j = i + 1; j < nums.Length - 1; j++) {
for (int k = j + 1; k < nums.Length; k++) {
if (nums[i] + nums[j] + nums[k] == 0) {
List<int> triplet = new List<int> { nums[i], nums[j], nums[k] };
// Check if triplet already exists
bool exists = result.Any(existing =>
existing.SequenceEqual(triplet)
);
if (!exists) {
result.Add(triplet);
}
}
}
}
}
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: If the first element is positive, we can break early since all remaining elements will also be positive.
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[] - All positive:
[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