Find all triplets with zero sum

Difficulty Level Medium
Frequently asked in Amazon GE Healthcare Google Hike
Array Hash Searching SortingViews 2690

The problem “Find all triplets with zero sum” states that you are given an array containing positive and negative number both. The problem statement asks to find out the triplet with the sum equal to 0.

Find all triplets with zero sum

Example

arr[] = {0,-2,1,3,2,-1}
(-2 -1  3) (-2 0  2) (-1 0  1)

Explanation

These are the triplets of whose sum is 0.

(-2 + -1 + 3 = 0) (-2 + 0 + 2=0)  (-1+ 0 + 1=0)

arr[] = {2,4,-5,-1,3}
(-5 2 3)

Explanation

These are the triplets of which numbers sum is 0 ⇒ -5 + 2 + 3 = 0

Algorithm

  1. Sort the given array.
  2. Set the Boolean variable isFound to false.
  3. Looping from i=0 to i<n-1
    1. Set fir=i+1, sec=n-1 and another variable x to the current array element.
    2. While fir<sec
      1. Check if three of the elements together form a sum of 0.
        1. If true, then print all three number and set isFound to true.
      2. Check if the sum of three elements(current array elements) is less than 0.
        1. If true, then increase the value of fir by 1.
      3. Check else if the sum of the three elements is greater than 0.
          1. If true, then decrease the value of sec by 1.
  4. Check if isFound remains false, that means no triplets can be formed.

Explanation

We are given an array. Then we are asked to determine the triplets that can be formed with the given numbers in an array whose sum is 0. We are going to use a nested loop. This algorithm can work in constant space. First, we are going to sort the array. This way we can use the two-pointer technique. We will declare one Boolean variable and set its value to false at first. This is just to ensure if we will not found any of the triplets which have elements sum to 0, the value of isFound remains to be false. Then we are going to update it to true whenever we find a triplet. So with this, we can conclude that no triplet is found.

We will sort the array first, in the nested loop. Then we traverse the array up to n-1. We will set the starting value as i+1, last value to n-1, and the x to the current value in the outer loop. In the inner loop we will traverse the values of an array, and check if the sum of all of the three elements (x + arr[fir] + arr[sec] ) is equal to 0 or not. If it is found to be 0, that means we have found the first pair and print all the current values of an array, and set isFound value to true.

This indicates we have found one of the pairs. If the sum of triplet is not equal to 0. We check if the sum of three current elements is less than 0. If the sum is less than 0. We increment fir, means our starting value is increased. If the condition isn’t satisfied. We check if the sum is greater than 0. If true, then decrement sec.

In this way, we are going to find all the possible triplets that can be sum to 0.

C++ code to Find all triplets with zero sum

#include<iostream>
#include<algorithm>

using namespace std;

void getTripletZero(int arr[], int n)
{
    bool isFound = false;
    sort(arr, arr+n);

    for (int i=0; i<n-1; i++)
    {
        int fir = i + 1;
        int sec = n - 1;
        int x = arr[i];
        while (fir < sec)
        {
            if (x + arr[fir] + arr[sec] == 0)
            {
                cout<<"("<<x<<" "<<arr[fir]<<" "<< arr[sec]<<")"<<endl;
                fir++;
                sec--;
                isFound = true;
            }
            else if (x + arr[fir] + arr[sec] < 0)
                fir++;
            else
                sec--;
        }
    }
    if (isFound == false)
        cout << " There is no triplet can be formed..!" << endl;
}
int main()
{
    int arr[] = {0,-2,1,3,2,-1};
    int n = sizeof(arr)/sizeof(arr[0]);
    getTripletZero(arr, n);
    return 0;
}

(-2 -1 3)
(-2 0 2)
(-1 0 1)

Java code to Find all triplets with zero sum

import java.util.Arrays;

class TripletSumzero
{
    public static void getTripletZero(int arr[], int n)
    {
        boolean isFound = false;

        Arrays.sort(arr);

        for (int i=0; i<n-1; i++)
        {
            int fir = i + 1;
            int sec = n - 1;
            int x = arr[i];
            while (fir < sec)
            {
                if (x + arr[fir] + arr[sec] == 0)
                {
                    System.out.println("(" + x + " "+arr[fir]+ " "+" "+arr[sec]+")");
                    fir++;
                    sec--;
                    isFound = true;
                }
                else if (x + arr[fir] + arr[sec] < 0)
                    fir++;
                else
                    sec--;
            }
        }
        if (isFound == false)
            System.out.println(" There is no triplet can be formed..!");
    }
    public static void main (String[] args)
    {
        int arr[] = {0,-2,1,3,2,-1};
        int n =arr.length;
        getTripletZero(arr, n);
    }
}

(-2 -1  3)
(-2 0  2)
(-1 0  1)

Complexity Analysis

Time Complexity

O(n2) where “n”  is the number of elements in the array. Since we are using two pointer technique that contributes for O(n) time. But the technique is itself used for O(n) time. Thus making the algorithm run in O(n^2) time.

Space Complexity

O(1) as no extra space is required.

Translate »