Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Example
2.
Brute Force Approach
2.1.
Complexity Analysis
3.
Optimized Approach (Two Pointer)
3.1.
Steps of Algorithm
3.2.
Implementation in C++
3.2.1.
Complexity Analysis
4.
Optimized Approach (HashMap Approach)
4.1.
Steps of Algorithm
4.2.
Implementation in C++
4.2.1.
Complexity Analysis
5.
Frequently Asked Question
5.1.
What is a stack?
5.2.
What is a map?
5.3.
What is the time complexity of push and pop operations in stack?
6.
Conclusion
Last Updated: Mar 27, 2024

Find all triplets with zero-sum

Author Ayush Tiwari
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

This blog will discuss three approaches to solve all triplets in an array with zero-sum.Before jumping on the approach to the problem, let us first understand the problem.

Must read about, kth largest element in an array and  Euclid GCD Algorithm

Problem Statement

Let say we have array nums of size n that contain both positive and negative integers, we have to return all the triplets [nums[i], nums[j], nums[k]], where 1<=i,j,k<=n such that i!= j, i!= k, and j!= k, and nums[i] + nums[j] + nums[k] == 0. return all the triplets [nums[i], nums[j], nums[k]].

Note: solution set must not contain duplicate triplets.

Sample Example

Input 1:

nums[] =  {-1,0,1,2,-1,-4}

 

Output 1: 

[{-1,-1,2},{-1,0,1}]

 

Explanation: 

sum of triplet nums[0], nums[4], nums[3] i.e -1 + -1 + 2 = 0
sum of triplet nums[0], nums[1], nums[2] i.e -1 + 0 + 1 = 0

 

Input 2: 

nums[] =  {1, 2, 3}

 

Output 2: 

[]

 

Explanation: 

There is no triplet with sum is zero

Brute Force Approach

The basic approach involves running three loops and checking if the total of three elements is zero or not one by one. Print elements if the sum of the three elements is 0(zero-sum); otherwise, print not found.

Complexity Analysis

Time Complexity: O(n3)

Since the approach consists of three nested traversal which is of the order O(n3).Therefore overall time complexity would be of order O(n3).

Space Complexity: O(1)

As the approach uses a constant space, therefore space complexity would be of order O(1)

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Optimized Approach (Two Pointer)

Requirements we need to fulfil: Find the triplets having sum = 0(zero-sum).

As array has both -ve and +ve numbers, firstly we sort the array. Sorted array would have -ve numbers together and +ve numbers together in an increasing order. This will make easy for searching the required numbers to make a 0 sum.

Base cases after sorting:

  1. If array size is < 3, means no triplet would exist from that array. Return empty vector of vectors.
  2. If first element is +ve, that means there is no -ve number by which we can make a 0 triplet sum. Return empty vector of vectors.
     

The basic thinking logic for this is: Fix any one number in sorted array and find the other two numbers after it. The other two numbers can be easily found using two pointers (as array is sorted) and two numbers should have sum = -1*(fixed number).

Steps of Algorithm

  1. Traverse the array and fix a number at every iteration.
  2. If number fixed is +ve, break there because we can't make it zero by searching after it.
  3. If number is getting repeated, ignore the lower loop and continue. This is for unique triplets. We want the last instance of the fixed number, if it is repeated.
  4. Make two pointers high and low, and initialize sum as 0.
  5. Search between two pointers, just similiar to binary search. Sum = num[i] + num[low] + num[high].
  6. If sum is -ve, means, we need more +ve numbers to make it 0, increament low (low++).
  7. If sum is +ve, means, we need more -ve numbers to make it 0, decreament high (high--).
  8. If sum is 0, that means we have found the required triplet, push it in answer vector.
  9. Now again, to avoid duplicate triplets, we have to navigate to last occurences of num[low] and num[high] respectively. Update the low and high with last occurences of low and high.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> threeSum(vector<int> &nums)
{
    sort(nums.begin(), nums.end()); // Sorted Array
    if (nums.size() < 3)
    { // Base case 1
        return {};
    }
    if (nums[0] > 0)
    { // Base case 2
        return {};
    }
    vector<vector<int>> answer;
    for (int i = 0; i < nums.size(); ++i)
    { // Traversing the array to fix the number.
        if (nums[i] > 0)
        { // If number fixed is +ve, stop there because we can't make it zero by searching after it.
            break;
        }
        if (i > 0 && nums[i] == nums[i - 1])
        { // If number is getting repeated, ignore the lower loop and continue.
            continue;
        }
        int low = i + 1, high = nums.size() - 1; // Make two pointers high and low, and initialize sum as 0.
        int sum = 0;
        while (low < high)
        { // Search between two pointers, just similiar to binary search.
            sum = nums[i] + nums[low] + nums[high];
            if (sum > 0)
            { // If sum is +ve, means, we need more -ve numbers to make it 0, decreament high (high--).
                high--;
            }
            else if (sum < 0)
            { // If sum is -ve, means, we need more +ve numbers to make it 0, increament low (low++).
                low++;
            }
            else
            {
                answer.push_back({nums[i], nums[low], nums[high]});                   // we have found the required triplet, push it in answer vector
                int last_low_occurence = nums[low], last_high_occurence = nums[high]; // Now again, to avoid duplicate triplets, we have to navigate to last occurences of num[low] and num[high] respectively
                while (low < high && nums[low] == last_low_occurence)
                { // Update the low and high with last occurences of low and high.
                    low++;
                }
                while (low < high && nums[high] == last_high_occurence)
                {
                    high--;
                }
            }
        }
    }
    return answer; // Return the answer vector.
}
int main()
{
    int n; // store the size of vector
    cin >> n;
    vector<int> nums(n); // vector of size n
    for (int i = 0; i < n; i++)
        cin >> nums[i];
    vector<vector<int>> ans = threeSum(nums);
    cout << "number of triplet with zero-sum: ";
    cout << ans.size() << endl;
    for (int i = 0; i < ans.size(); i++)
    {
        for (auto element : ans[i])
            cout << element << ' ';
        cout << endl;
    }
}

 

Input: 

6
-1 0 1 2 -1 -4

 

Output: 

number of triplet with zero-sum: 2
-1 -1 2 
-1 0 1

 

Complexity Analysis

Time Complexity: O(n2)

Since the approach consists of finding a pair in one loop then finding the triplet with zero sum.Therefore overall time complexity would be of order O(n2).

Space Complexity: O(1)

We Cannot uses any extra space so in worst case space coplexity is O(1).

Check out this array problem - Merge 2 Sorted Arrays

Optimized Approach (HashMap Approach)

Requirements we need to fulfil: Find the triplets having sum = 0(zero-sum).

As array has both -ve and +ve numbers, firstly we sort the array. Sorted array would have -ve numbers together and +ve numbers together in an increasing order. This will make easy for searching the required numbers to make a 0 sum.

Base cases after sorting:

  1. If array size is < 3, means no triplet would exist from that array. Return empty vector of vectors.
  2. If first element is +ve, that means there is no -ve number by which we can make a 0 triplet sum. Return empty vector of vectors.
     

In this approach, firstly, we will hash the indices of all elements in a hashMap. In case of repeated elements, the last occurence index would be stored in hashMap.

Steps of Algorithm

  1. Here also we fix a number (num[i]), by traversing the loop. But the loop traversal here for fixing numbers would leave last two indices. These last two indices would be covered by the nested loop.
  2. If number fixed is +ve, break there because we can't make it zero by searching after it.
  3. Make a nested loop to fix a number after the first fixed number. (num[j])
  4. To make sum 0, we would require the -ve sum of both fixed numbers. Let us say this required.
  5. Now, we will find the this required number in hashMap. If it exists in hashmap and its last occurrence index > 2nd fixed index, we found our triplet. Push it in answer vector.
  6. Update j to last occurence of 2nd fixed number to avoid duplicate triplets.
  7. Update i to last occurence of 1st fixed number to avoid duplicate triplets.
  8. Return answer vector.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> threeSum(vector<int> &nums)
{
    sort(nums.begin(), nums.end()); // Sorted Array
    if (nums.size() < 3)
    { // Base Case 1
        return {};
    }
    if (nums[0] > 0)
    { // Base Case 2
        return {};
    }
    unordered_map<int, int> hashMap;
    for (int i = 0; i < nums.size(); ++i)
    { // Hashing of Indices
        hashMap[nums[i]] = i;
    }
    vector<vector<int>> answer;
    for (int i = 0; i < nums.size() - 2; ++i)
    { // Traversing the array to fix the number.
        if (nums[i] > 0)
        { // If number fixed is +ve, stop there because we can't make it zero by searching after it.
            break;
        }
        for (int j = i + 1; j < nums.size() - 1; ++j)
        {                                            // Fixing another number after first number
            int required = -1 * (nums[i] + nums[j]); // To make sum 0, we would require the -ve sum of both fixed numbers.
            if (hashMap.count(required) && hashMap.find(required)->second > j)
            { // If it exists in hashmap and its last occurrence index > 2nd fixed index, we found our triplet.
                answer.push_back({nums[i], nums[j], required});
            }
            j = hashMap.find(nums[j])->second; // Update j to last occurence of 2nd fixed number to avoid duplicate triplets.
        }
        i = hashMap.find(nums[i])->second; // Update i to last occurence of 1st fixed number to avoid duplicate triplets.
    }
    return answer; // Return answer vector.
}
int main()
{
    int n; // store the size of vector
    cin >> n;
    vector<int> nums(n); // vector of size n
    for (int i = 0; i < n; i++)
        cin >> nums[i];
    vector<vector<int>> ans = threeSum(nums);
    cout << "number of triplet with zero-sum: ";
    cout << ans.size() << endl;
    for (int i = 0; i < ans.size(); i++)
    {
        for (auto element : ans[i])
            cout << element << ' ';
        cout << endl;
    }
}

 

Input: 

6
-1 0 1 2 -1 -4

 

Output: 

number of triplet with zero-sum: 2
-1 -1 2 
-1 0 1

 

Complexity Analysis

Time Complexity: O(n2)

Since the approach consists of finding a pair in one loop then finding the triplet with zero sum.Therefore overall time complexity would be of order O(n2).

Space Complexity: O(n)

For storing the element in hash map.

Frequently Asked Question

What is a stack?

A stack is a linear data structure which comprises homogeneous elements and works on the principle of last in first out.That means,one which goes in last will come out first.

What is a map?

A map is like a dictionary where elements are stored in key-value manner.It stores the elements in the sorted order of keys.

What is the time complexity of push and pop operations in stack?

The time complexity of push and pop operations is O(1) since it takes a constant amount of time to either push an element in the top or pop the top element and reduce size by one.

Conclusion

This article discussed the approach to find all triplet with sum zero in array of both positive and negative value.First a brute force then we move to two optimal approach using two pointer method and hashing.

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem DesignMachine learning and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!!

Previous article
Find Smallest Missing Positive Integer
Next article
Find all elements in an array which have at-least two greater elements.
Live masterclass