Open In App

3 Sum - Find All Triplets with Zero Sum

Last Updated : 14 Feb, 2025
Suggest changes
Share
Like Article
Like
Report

Given an array arr[], the task is to find all possible indices {i, j, k} of triplet {arr[i], arr[j], arr[k]} such that their sum is equal to zero and all indices in a triplet should be distinct (i != j, j != k, k != i). We need to return indices of a triplet in sorted order, i.e., i < j < k.

Examples :

Input: arr[] = {0, -1, 2, -3, 1}
Output: {{0, 1, 4}, {2, 3, 4}}
Explanation:  Two triplets with sum 0 are:
arr[0] + arr[1] + arr[4] = 0 + (-1) + 1 = 0
arr[2] + arr[3] + arr[4] = 2 + (-3) + 1 = 0

Input: arr[] = {1, -2, 1, 0, 5}
Output: {{0, 1, 2}}
Explanation: Only triplet which satisfies the condition is arr[0] + arr[1] + arr[2] = 1 + (-2) + 1 = 0

Input: arr[] = {2, 3, 1, 0, 5}
Output: {{}}
Explanation: There is no triplet with sum 0

Table of Content

[Naive Approach] Using Three Nested Loops - O(n^3) Time and O(1) Space

The simplest approach is to generate all possible triplets using three nested loops and if the sum of any triplet is equal to zero then add it to the result. 

C++ 
// C++ program to find triplet having sum zero using // three nested loops #include <iostream> #include <vector> using namespace std; vector<vector<int>> findTriplets(vector<int> &arr) {  vector<vector<int>> res;   int n = arr.size();   // Generating all triplets  for (int i = 0; i < n - 2; i++) {  for (int j = i + 1; j < n - 1; j++) {  for (int k = j + 1; k < n; k++) {  // If the sum of a triplet equals to zero  // then add it's indices to the result  if (arr[i] + arr[j] + arr[k] == 0)   res.push_back({i, j, k});  }  }  }  return res;  } int main() {  vector<int> arr = {0, -1, 2, -3, 1};  vector<vector<int>> res = findTriplets(arr);  for(int i = 0; i < res.size(); i++)  cout << res[i][0] << " " << res[i][1] << " " << res[i][2] << endl;    return 0; }
C 
// C program to find triplet having sum zero using  // three nested loops #include <stdio.h> #include <stdlib.h> #define MAX_LIMIT 100  void findTriplets(int arr[], int n, int res[][3], int* count) {  *count = 0;   // Generating all triplets  for (int i = 0; i < n - 2; i++) {  for (int j = i + 1; j < n - 1; j++) {  for (int k = j + 1; k < n; k++) {    // If the sum of triplet equals zero  // then add it's indexes to reuslt  if (arr[i] + arr[j] + arr[k] == 0) {  res[*count][0] = i;  res[*count][1] = j;  res[*count][2] = k;  (*count)++;   }  }  }  } } int main() {  int arr[] = {0, -1, 2, -3, 1};  int n = sizeof(arr) / sizeof(arr[0]);    // res array to store all triplets  int res[MAX_LIMIT][3];     // Variable to store number of triplets found  int count = 0;   findTriplets(arr, n, res, &count);  for (int i = 0; i < count; i++)   printf("%d %d %d\n", res[i][0], res[i][1], res[i][2]);    return 0; }
Java 
// Java program to find triplet having sum zero using  // three nested loops import java.util.ArrayList; import java.util.List; class GfG {  static ArrayList<ArrayList<Integer>> findTriplets(int[] arr) {  ArrayList<ArrayList<Integer>> res = new ArrayList<>();  int n = arr.length;  // Generating all triplets  for (int i = 0; i < n - 2; i++) {  for (int j = i + 1; j < n - 1; j++) {  for (int k = j + 1; k < n; k++) {    // If the sum of triplet equals to zero  // then add it's indexes to the result  if (arr[i] + arr[j] + arr[k] == 0) {  ArrayList<Integer> triplet = new ArrayList<>();  triplet.add(i);  triplet.add(j);  triplet.add(k);  res.add(triplet);  }  }  }  }  return res;  }  public static void main(String[] args) {  int[] arr = {0, -1, 2, -3, 1};  ArrayList<ArrayList<Integer>> res = findTriplets(arr);  for (List<Integer> triplet : res)   System.out.println(triplet.get(0) + " " + triplet.get(1)  + " " + triplet.get(2));  } }
Python 
# Python program to find triplet with sum zero # using three nested loops def findTriplets(arr): res = [] n = len(arr) # Generating all triplets for i in range(n - 2): for j in range(i + 1, n - 1): for k in range(j + 1, n): # If the sum of triplet equals to zero # then add it's indexes to the result if arr[i] + arr[j] + arr[k] == 0: res.append([i, j, k]) return res arr = [0, -1, 2, -3, 1] res = findTriplets(arr) for triplet in res: print(triplet[0], triplet[1], triplet[2])
C# 
// C# program to find triplet with sum zero using  // three nested loops using System; using System.Collections.Generic; class GfG {  static List<List<int>> FindTriplets(int[] arr) {  List<List<int>> res = new List<List<int>>();  int n = arr.Length;  // Generating all triplets  for (int i = 0; i < n - 2; i++) {  for (int j = i + 1; j < n - 1; j++) {  for (int k = j + 1; k < n; k++) {    // If the sum of triplet equals to zero  // then add it's indexes to the result  if (arr[i] + arr[j] + arr[k] == 0) {  res.Add(new List<int> { i, j, k });  }  }  }  }  return res;  }  public static void Main() {  int[] arr = { 0, -1, 2, -3, 1 };  List<List<int>> res = FindTriplets(arr);  foreach (var triplet in res) {  Console.WriteLine($"{triplet[0]} {triplet[1]} {triplet[2]}");  }  } }
JavaScript 
// JavaScript program to find triplet with sum zero  // using three nested loops function findTriplets(arr) {  const res = [];  const n = arr.length;  // Generating all triplets  for (let i = 0; i < n - 2; i++) {  for (let j = i + 1; j < n - 1; j++) {  for (let k = j + 1; k < n; k++) {    // If the sum of triplet equals to zero  // then add it's indexes to the result  if (arr[i] + arr[j] + arr[k] === 0) {  res.push([i, j, k]);  }  }  }  }  return res; } const arr = [0, -1, 2, -3, 1]; const res = findTriplets(arr); res.forEach(triplet => {  console.log(triplet[0] + " " + triplet[1] + " " + triplet[2]); });

Output
0 1 4 2 3 4

Time Complexity: O(n3), As three nested loops are used.
Auxiliary Space: O(1)

[Expected Approach] Using Hash Map - O(n^3) Time and O(n) Space

  • The idea is to use a hash map to store indices of each element and efficiently find triplets that sum to zero.
  • We iterate through all pairs (j, k), compute the required third element as -(arr[j] + arr[k]), and check if it exists in the map with a valid index i < j.
  • If found, we store {i, j, k} in the result. To ensure unique triplets, the map maintains only indices less than the current j.
  • In the worst case, this approach also takes O(n^3) time but in the average case, it is much faster than Naive approach as we are iterating over only those triplets whose sum is equal to target.
C++ 
 // C++ program to find all triplets with zero sum #include <bits/stdc++.h> using namespace std; vector<vector<int>> findTriplets(vector<int> &arr) {    // Map to store indices for each value  unordered_map<int, vector<int>> map;    // Resultant array   vector<vector<int>> ans;    // Check for all pairs i, j  for (int j=0; j<arr.size(); j++) {  for (int k=j+1; k<arr.size(); k++) {    // Value of third index should be   int val = -1*(arr[j]+arr[k]);    // If such indices exists  if (map.find(val)!=map.end()) {    // Append the i, j, k  for (auto i: map[val]) {  ans.push_back({i, j, k});  }  }  }    // After j'th index is traversed  // We can use it as i.  map[arr[j]].push_back(j);  }    return ans; } int main() {  vector<int> arr = {0, -1, 2, -3, 1};  vector<vector<int>> res = findTriplets(arr);  for (int i = 0; i < res.size(); i++)  cout << res[i][0] << " " << res[i][1] << " " << res[i][2] << endl;  return 0; }
Java 
// Java program to find all triplets with zero sum import java.util.*; class GfG {  // Function to find all triplets with zero sum  static List<List<Integer>> findTriplets(int[] arr) {    // Map to store indices for each value  HashMap<Integer, List<Integer>> map = new HashMap<>();    // Resultant list  List<List<Integer>> ans = new ArrayList<>();    // Check for all pairs i, j  for (int j = 0; j < arr.length; j++) {  for (int k = j + 1; k < arr.length; k++) {    // Value of third index should be   int val = -1 * (arr[j] + arr[k]);    // If such indices exist  if (map.containsKey(val)) {    // Append the i, j, k  for (int i : map.get(val)) {  ans.add(Arrays.asList(i, j, k));  }  }  }    // After j'th index is traversed  // We can use it as i.  map.putIfAbsent(arr[j], new ArrayList<>());  map.get(arr[j]).add(j);  }    return ans;  }  public static void main(String[] args) {  int[] arr = {0, -1, 2, -3, 1};  List<List<Integer>> res = findTriplets(arr);  for (List<Integer> triplet : res) {  System.out.println(triplet.get(0) + " " + triplet.get(1) + " " + triplet.get(2));  }  } }
Python 
# Python program to find all triplets with zero sum # Function to find all triplets with zero sum def findTriplets(arr): # Map to store indices for each value map = {} # Resultant array ans = [] # Check for all pairs i, j for j in range(len(arr)): for k in range(j + 1, len(arr)): # Value of third index should be  val = -1 * (arr[j] + arr[k]) # If such indices exist if val in map: # Append the i, j, k for i in map[val]: ans.append([i, j, k]) # After j'th index is traversed # We can use it as i. if arr[j] not in map: map[arr[j]] = [] map[arr[j]].append(j) return ans if __name__ == "__main__": arr = [0, -1, 2, -3, 1] res = findTriplets(arr) for triplet in res: print(triplet[0], triplet[1], triplet[2])
C# 
// C# program to find all triplets with zero sum using System; using System.Collections.Generic; class GfG {  // Function to find all triplets with zero sum  static List<List<int>> findTriplets(int[] arr) {    // Dictionary to store indices for each value  Dictionary<int, List<int>> map = new Dictionary<int, List<int>>();    // Resultant list  List<List<int>> ans = new List<List<int>>();    // Check for all pairs i, j  for (int j = 0; j < arr.Length; j++) {  for (int k = j + 1; k < arr.Length; k++) {    // Value of third index should be   int val = -1 * (arr[j] + arr[k]);    // If such indices exist  if (map.ContainsKey(val)) {    // Append the i, j, k  foreach (int i in map[val]) {  ans.Add(new List<int> { i, j, k });  }  }  }    // After j'th index is traversed  // We can use it as i.  if (!map.ContainsKey(arr[j])) {  map[arr[j]] = new List<int>();  }  map[arr[j]].Add(j);  }    return ans;  }  static void Main(string[] args) {  int[] arr = { 0, -1, 2, -3, 1 };  List<List<int>> res = findTriplets(arr);  foreach (var triplet in res) {  Console.WriteLine(triplet[0] + " " + triplet[1] + " " + triplet[2]);  }  } }
JavaScript 
// JavaScript program to find all triplets with zero sum // Function to find all triplets with zero sum function findTriplets(arr) {    // Map to store indices for each value  let map = new Map();    // Resultant array  let ans = [];    // Check for all pairs i, j  for (let j = 0; j < arr.length; j++) {  for (let k = j + 1; k < arr.length; k++) {    // Value of third index should be   let val = -1 * (arr[j] + arr[k]);    // If such indices exist  if (map.has(val)) {    // Append the i, j, k  for (let i of map.get(val)) {  ans.push([i, j, k]);  }  }  }    // After j'th index is traversed  // We can use it as i.  if (!map.has(arr[j])) {  map.set(arr[j], []);  }  map.get(arr[j]).push(j);  }    return ans; } const arr = [0, -1, 2, -3, 1]; const res = findTriplets(arr); for (let triplet of res) {  console.log(triplet[0], triplet[1], triplet[2]); }

Output
0 1 4 2 3 4

Time Complexity: O(n3), Since two nested loops are used and traversing through the map may take O(n) in worst case.
Auxiliary Space: O(n), Since a HashMap is used to store all value index pairs.

Please refer 3Sum - Complete Tutorial for all list of problems on triplets in an array.


Next Article
Find the element before which all the elements are smaller than it, and after which all are greater

K

kartik

Similar Reads

Article Tags :
Practice Tags :
We use cookies to ensure you have the best browsing experience on our website. By using our site, you acknowledge that you have read and understood our Cookie Policy & Privacy Policy  Cookies are not collected in the GeeksforGeeks mobile applications.
Lightbox