Searching: Find all the triplets with zero sum

Problem Statement:

You are given an array, you need to find all the possible index of triplet, such that the sum is equal to zero.

Example:

Input: a [0, -1, 2, -3, 1]

Output:

{0, 1, 4}

{2, 3, 4}

Solution 1: Brute force approach

Take 3 nested for loop and check if any triplet is equal to zero print the result

Time Complexity: O(n^3)
Space Complexity: O(1)

Solution 2: Hash Map approach

Use hash map to store index of each element and find the triplets that sum to zero,

Time Complexity: O(n^3)
Space Complexity: O(n)

Code Solution

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <limits.h>

using namespace std;

vector<vector<int>> solution_1 (vector<int> &arr) 
{

    vector<vector<int>> result; 
    int n = arr.size(); 

    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 (arr[i] + arr[j] + arr[k] == 0) 
                    result.push_back({i, j, k});
            }
        }
    }
    return result; 
}


vector<vector<int>> solution_2 (vector<int> &arr) 
{
    
    unordered_map<int, vector<int>> map;
    
    vector<vector<int>> result;
    
    for (int j=0; j<arr.size(); j++) 
    {
        for (int k=j+1; k<arr.size(); k++) 
        {
            
            int val = -1*(arr[j]+arr[k]);
            
            if (map.find(val)!=map.end()) 
            {
                
                for (auto i: map[val]) 
                {
                    result.push_back({i, j, k});
                }
            }
        }
        
        map[arr[j]].push_back(j);
    }
    
    return result;
}

int main() 
{
    vector<int> arr = {0, -1, 2, -3, 1};

    vector<vector<int>> res = solution_1(arr);
    for(int i = 0; i < res.size(); i++)
        cout << res[i][0] << " " << res[i][1] << " " << res[i][2] << endl;

    cout<<"\n";

    res = solution_2(arr);
    for(int i = 0; i < res.size(); i++)
        cout << res[i][0] << " " << res[i][1] << " " << res[i][2] << endl;


    return 0;
}

Output

0 1 4
2 3 4

0 1 4
2 3 4