.png)
Find All Triplets With Zero Sum (3Sum)
Problem Statement
You are given an integer array arr.
Your task is to find all unique triplets (a, b, c) such that:
a + b + c = 0
⚠️ The solution set must not contain duplicate triplets.
Example 1
Input
arr = [-1,0,1,2,-1,-4]
Output
[[-1,-1,2], [-1,0,1]]
Example 2
Input
arr = [0,1,1]
Output
[]
Example 3
Input
arr = [0,0,0]
Output
[[0,0,0]]
Why This Problem Is Important
- One of the most asked interview questions
- Builds foundation for 2-pointer technique
- Teaches sorting + duplicate handling
- Asked in FAANG, MAANG, product-based companies
- Extension of Two Sum & Subarray problems
Approaches Overview
| Approach | Technique | Time | Space |
|---|---|---|---|
| Approach 1 | Brute Force | O(n³) | O(1) |
| Approach 2 | Hashing (Two Sum for each i) | O(n²) | O(n) |
| Approach 3 | Sorting + Two Pointers (Optimal) | O(n²) | O(1) |
Approach 1: Brute Force
Idea
Check all possible triplets and store those whose sum equals 0.
Algorithm
- Loop i from 0 → n-3
- Loop j from i+1 → n-2
- Loop k from j+1 → n-1
- If arr[i] + arr[j] + arr[k] == 0, store triplet
- Remove duplicates manually
Time & Space Complexity
- Time: O(n³)
- Space: O(1) (excluding output)
C
#include
int main() {
int arr[] = {-1,0,1,2,-1,-4};
int n = 6;
for(int i=0;iC++
#include
using namespace std;
int main() {
int arr[] = {-1,0,1,2,-1,-4};
int n = 6;
for(int i=0;iJava
public class ThreeSum {
public static void main(String[] args) {
int[] arr = {-1,0,1,2,-1,-4};
int n = arr.length;
for(int i=0;iPython
arr = [-1,0,1,2,-1,-4]
for i in range(len(arr)):
for j in range(i+1, len(arr)):
for k in range(j+1, len(arr)):
if arr[i] + arr[j] + arr[k] == 0:
print(arr[i], arr[j], arr[k])
JavaScript
let arr = [-1,0,1,2,-1,-4];
let n = arr.length;
for(let i=0;iC#
using System;
class Program {
static void Main() {
int[] arr = {-1,0,1,2,-1,-4};
int n = arr.Length;
for(int i=0;iOutput
-1 0 1
-1 2 -1
0 1 -1
Approach 2: Hashing (Two Sum for Each Element)
Idea
Fix one element and solve Two Sum using a hash set for the remaining array.
Algorithm
- Fix index i
- Use a hash set to find pairs summing to -arr[i]
- Avoid duplicates
Time & Space Complexity
- Time: O(n²)
- Space: O(n)
Python
arr = [-1,0,1,2,-1,-4]
res = set()
for i in range(len(arr)):
seen = set()
for j in range(i+1, len(arr)):
target = -arr[i] - arr[j]
if target in seen:
res.add(tuple(sorted([arr[i], arr[j], target])))
seen.add(arr[j])
print(list(res))
Java
import java.util.*;
public class ThreeSum {
public static void main(String[] args) {
int[] arr = {-1,0,1,2,-1,-4};
Set> res = new HashSet<>();
for(int i=0;i set = new HashSet<>();
for(int j=i+1;j temp = Arrays.asList(arr[i], arr[j], target);
Collections.sort(temp);
res.add(temp);
}
set.add(arr[j]);
}
}
System.out.println(res);
}
}
C++
#include
using namespace std;
int main() {
vector arr = {-1,0,1,2,-1,-4};
set> res;
for(int i=0;i seen;
for(int j=i+1;j temp = {arr[i], arr[j], target};
sort(temp.begin(), temp.end());
res.insert(temp);
}
seen.insert(arr[j]);
}
}
for(auto &v : res){
cout << "[";
for(int i=0;iJavaScript
let arr = [-1,0,1,2,-1,-4];
let res = new Set();
for(let i=0;ia-b);
res.add(JSON.stringify(triplet));
}
seen.add(arr[j]);
}
}
let output = Array.from(res).map(x => JSON.parse(x));
console.log(output);
C#
using System;
using System.Collections.Generic;
class Program {
static void Main() {
int[] arr = {-1,0,1,2,-1,-4};
HashSet res = new HashSet();
for(int i=0;i seen = new HashSet();
for(int j=i+1;jOutput
Unique triplets whose sum is 0:
[-1, -1, 2]
[-1, 0, 1]
Approach 3: Sorting + Two Pointers (Optimal)
Idea
Sort the array and use two pointers to find pairs for each fixed element.
Algorithm
- Sort the array
- Fix index i
- Use left = i+1, right = n-1
- Adjust pointers based on sum
- Skip duplicates
Time & Space Complexity
- Time: O(n²)
- Space: O(1)
Implementations
C++
#include
using namespace std;
int main() {
vector arr = {-1,0,1,2,-1,-4};
sort(arr.begin(), arr.end());
int n = arr.size();
for(int i = 0; i < n; i++) {
if(i > 0 && arr[i] == arr[i-1]) continue;
int l = i + 1, r = n - 1;
while(l < r) {
int sum = arr[i] + arr[l] + arr[r];
if(sum == 0) {
cout << "[" << arr[i] << ", " << arr[l] << ", " << arr[r] << "] ";
l++; r--;
while(l < r && arr[l] == arr[l-1]) l++;
while(l < r && arr[r] == arr[r+1]) r--;
}
else if(sum < 0) l++;
else r--;
}
}
return 0;
}
Python
arr = [-1,0,1,2,-1,-4]
arr.sort()
res = []
for i in range(len(arr)):
if i > 0 and arr[i] == arr[i-1]:
continue
l, r = i+1, len(arr)-1
while l < r:
s = arr[i] + arr[l] + arr[r]
if s == 0:
res.append([arr[i], arr[l], arr[r]])
l += 1
r -= 1
while l < r and arr[l] == arr[l-1]:
l += 1
while l < r and arr[r] == arr[r+1]:
r -= 1
elif s < 0:
l += 1
else:
r -= 1
print(res)
JavaScript
let arr = [-1,0,1,2,-1,-4];
arr.sort((a,b)=>a-b);
let res = [];
for(let i=0;i0 && arr[i]===arr[i-1]) continue;
let l=i+1, r=arr.length-1;
while(lJava
import java.util.*;
public class ThreeSum {
public static void main(String[] args) {
int[] arr = {-1,0,1,2,-1,-4};
Arrays.sort(arr);
int n = arr.length;
for(int i=0;i0 && arr[i]==arr[i-1]) continue;
int l=i+1, r=n-1;
while(lC#
using System;
class Program {
static void Main() {
int[] arr = {-1,0,1,2,-1,-4};
Array.Sort(arr);
int n = arr.Length;
for(int i=0;i0 && arr[i]==arr[i-1]) continue;
int l=i+1, r=n-1;
while(lOutput
[-1, -1, 2]
[-1, 0, 1]
Summary
- Brute force checks all triplets
- Hashing improves to O(n²) but uses space
- Sorting + Two Pointers is optimal & interview preferred
- Duplicate handling is key interview discussion point
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
