Triplet with zero sum

Difficulty: Medium, Asked-in: Google, Amazon, Facebook, Microsoft

Key takeaway: An excellent problem to learn problem-solving using hashing and two pointers approach.

Let’s understand the problem

Given an array X[] of distinct elements, write a program to find all the unique triplets in the array whose sum is equal to zero. For example, suppose such triplets in the array are X[i], X[j] and X[k] then X[i] + X[j] + X[k] = 0. Note : solution set must not contain duplicate triplets.

Examples

Input: X[] = [0, -2, 5, -3, 2], Output: [0, -2, 2], [-2, 5, -3] Explanation : The triplets with zero sum are 0 + (-2) + 2 = 0 and (-2) + 5 + (-3) = 0

Input: X[] = [-1, 0, 1, 2, -1, -4], Output: [-1, -1, 2],[-1, 0, 1]

Discussed solution approaches

  • A brute force approach  using three nested loops
  •  Using a hash table
  • An efficient solution  using the sorting and two-pointer

A brute force approach  using three nested loops

The basic solution idea is to find out each possible triplet and check whether their sum is equal to zero or not. We can implement this using three nested loops.

Solution Pseudocode C++

vector<vector<int>> findTripletSum(vector<int>& X) 
{
    vector<vector<int>> output
    int n = X.size()
    if(n <=2)
        return output
        
     for(int i = 0; i < n - 2; i = i + 1)
     {  
        for(int j = i + 1; j < n - 1; j = j + 1)
        {
            for(int k = j + 1; k < n; k = k + 1)
            {
                if(X[i] + X[j] + X[k] == 0)
                {  
                    vector<int> triplet = {X[i], X[j], X[k]}
                    output.push_back(triplet)
                }
            }
        }
    }
    return output
}

Time and space complexity analysis

  • We are running three nested loops, so time complexity = O(n³).
  • We are using constant extra space, so space complexity = O(1).

Using a hash table

Solution Idea

The previous approach works very slow because of O(n³) Time Complexity. This can be optimized to work with less time complexity using a hash table. The idea is to traverse the array and for every element X[i], we find a pair with a sum equal to – X[i]. In other words, we explore every pair of elements (X[i], X[j]) using nested loops and search for the value -(X[i] + X[j]) in the hash table.

Solution Steps

  1. We run two nested loops to explore every pair of elements: inner loop from i+1 to n-1 and outer loop from 0 to n-2.
  2. Inside the inner loop, we create a hash set to track the element with the sum = -(X[i] + X[j]).

    • Check if the negative of the sum of ith and jth element is present in the hash-map. If the element is present then we insert the triplets (sum, X[i], X[j]) in a set output, that is used to store the unique solutions.
    • If sum = -(X[i] + X[j]) not present in the hash table, then we insert the value X[j] into the hash set.
  3. By end of the nested loops, we return the set output

Solution Pseudocode C++

vector<vector<int>> findTripletSum(vector<int>& X) 
{
    vector<vector<int>> output
    int n = X.size()
    if(n <=2)       
        return output
    
    for (int i = 0; i < n - 1; i = i + 1) 
    {
        unordered_set<int> s
        for (int j = i + 1; j < n; j = j + 1) 
        {
            int sum = - (X[i] + X[j])
            if (s.find(sum) != s.end()) 
            {
                vector<int> triplet = {sum, X[i], X[j]}
                output.insert(triplet)
            }
            else
                s.insert(X[j])
        }
    }
    return output
}

Time and space complexity analysis

Time Complexity is O (n²) since the algorithm is using two nested loops and space complexity is O(n), for hash-map.

An efficient solution  using the sorting and two-pointers

Solution Idea

The previous approach requires an extra space because of the hash table. This can be further optimized to work with constant space using two pointer approach.

The idea is to first sort the array and traverse the array from left to right. Now for each element X[i], we use two pointers l (initialized with i + 1) and r (initialized with n - 1) and run a loop until r > l to find out if there are any triplets (X[i], X[l], X[r]) having a sum equal to zero is present or not.

In another way: we sort an input array and run through all indices of a possible first element of a triplet. For each possible first element, we use a bi-directional two-pointers approach similar to the pair sum problem in the remaining part of the array.

Solution Steps

  • Sort the array in increasing order.
  • Now we traverse the array using a loop from i = 0 to n - 2.
  • For each element X[i], we run a two-pointer loop until r > l.
  • Inside the two-pointers loop, we calculate the sum of the triplet (X[i], X[l], X[r]).
  • If (sum = 0), then we insert the result into the output vector.
  • If (sum > 0), we decrement the right pointer r by 1 i.e. because the array is sorted we move the right pointer to get the smaller sum value.
  • If (sum < 0), we increment the left pointer l by 1 i.e. we move the left pointer to get the larger sum value.
  • By end of the nested loops, we return the output vector.

Solution Pseudocode C++

vector<vector<int>> findTripletSum(vector<int>& X) 
{
    int n = X.size()
    sort(X.begin(), X.end())
    vector<vector<int>> output
    if(X.size() <= 2)
        return output
        
    for(int i = 0; i < n - 2; i = i + 1)
    {
        int l = i + 1, r = n - 1
        while(r > l)
        {
            int sum = X[i] + X[l] + X[r]
            if(s > 0)
                r = r - 1
            else if(sum < 0)
                l = l + 1
            else
            {                                   
                vector<int> triplet = {X[i], X[l], X[r]}
                output.push_back(triplet)
                l = l + 1
                r = r - 1
            }
        }
    }
    return output
}

Time and space complexity analysis

  • We are using two nested loops and doing a constant number of operations at each iteration. So time complexity = O(n²).
  • We are using constant extra space, so space complexity = O(1).

Critical ideas to think!

  •  What do you need to change in the approach to find all the triplets smaller than a given value?
  • Can you extend this to find all subsets of elements having four elements with a given sum value?
  • How do we modify the above code if duplicate values are allowed?

Suggested coding questions to practice

Enjoy learning! Enjoy Algorithms!

We welcome your comments

Subscribe Our Newsletter

Get well-designed application and interview centirc content on ds-algorithms, machine learning, system design and oops. Content will be delivered weekly.