Find all Triplets that Sum to Zero

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 triplets in array whose sum is equal to zero. For example, suppose triplets that sum to zero are X[i], X[j] and X[k] then X[i] + X[j] + X[k] = 0.

Example 1

Input: X[] = [0, -2, 5, -3, 2], Output: [0, -2, 2] and [-2, 5, -3]

Explanation: Among several triplets, two triplets have zero-sum i.e. [0, -2, 2] and [-2, 5, -3].

Example 2

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

Explanation: Among several triplets, three triplets have zero-sum i.e. [-2, 6, -4], [-1, 1, 0] and [-2, 2, 0].

Example 3

Input: X[] = [-3, 6, -1, 1], Output: "triplet with 0 sum does not exist"

Discussed solution approaches

• Brute force approach using three nested loops
• Using two nested loops and hash table
• Efficient solution using sorting and two-pointers

Brute force approach  using three nested loops

The basic idea would be to explore each possible triplet and check whether the triplet sum is equal to zero or not. We can implement this using three nested loops.

• Outer loop from i = 0 to n - 3 to track the first element of triplet.
• Inner loop from j = i to n - 2 to track the second element of triplet.
• Innermost loop from k = j to n - 1 to track the third element of triplet.

At each iteration, we calculate the sum of X[i], X[j] and X[k]. If the triplet sum equals zero, we print all three elements as an output. Otherwise, we move to the next iteration.

There may be a case when zero sum triplet is not present in the array. How can we identify such situations? One idea would be to use a boolean flag.

Suppose we initialize a boolean flag tripletFound to false before starting nested loops. When we find any triplet with sum equal to zero, we update this flag to true. Otherwise, if tripletFound is still false by the end of loop, then there is no such triplet, and we print "triplet with 0 sum does not exist".

Solution code C++

void findTripletSum(int X[], int n) 
{
    bool tripletFound = false;

    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)
                {  
                    cout << X[i] << " " << X[j] << " " << X[k] << endl;
                    tripletFound = true;
                }
            }
        }
    }
    if (tripletFound == false) 
        cout << "triplet with 0 sum does not exist" << endl;
}

Solution code Python

def findTripletSum(X, n):
    tripletFound = False
    for i in range(n - 2):
        for j in range(i + 1, n - 1):
            for k in range(j + 1, n):
                if X[i] + X[j] + X[k] == 0:
                    print(X[i], X[j], X[k])
                    tripletFound = True
    if not tripletFound:
        print("triplet with 0 sum does not exist")

Solution analysis

We are running three nested loops, so time complexity = O(n³). In another way, we explore each triplet in the array. So total number of loop iterations = Total number of triplets in array of size n = nC3 = n(n-1)(n-2)/6 = O(n^3). Note: We are ignoring lower-order terms and coefficients.

At each iteration, we are doing constant operations. So time complexity = O(n^3) * O(1) = O(n^3).We use constant extra space, so space complexity = O(1).

Triplet sum solution using hash table

Solution idea

How can we improve the time complexity? This is a searching problem. Can we think of improving time complexity further using a hash table?

The idea is to traverse the array, and for every element X[i], we search a pair (excluding element X[i]) with sum equal to –X[i]. In other words, we explore every pair of elements (X[i], X[j]) using nested loop and search for the value -(X[i] + X[j]) in hash table.

Solution steps

Step 1: We initialize a boolean flag tripletFound to false before starting the nested loop.

Step 2: We run two nested loops to explore every pair of elements (X[i], X[j]). Here outer loop run from i = 0 to n - 2 and inner loop run from j = i + 1 to n - 1.

Step 3: Before starting the inner loop, we create a hash table to store and track elements with value equal to -(X[i] + X[j]). Inside the inner loop:

• If value -(X[i] + X[j]) is present in the hash table, we have found a triplet with zero sum. So we print all three elements X[i], X[j] and -(X[i] + X[j]). We also update the boolean flag tripletFound as true.
• Otherwise, we insert X[j] into the hash table.

Step 4: If tripletFound is still false by the end of loop, we print "triplet with 0 sum does not exist".

Solution pseudocode

void findTripletSum(int X[], int n) 
{
    bool tripletFound = false
    for (int i = 0; i < n - 1; i = i + 1) 
    {
        hash table H
        for (int j = i + 1; j < n; j = j + 1) 
        {
            int sum = -(X[i] + X[j])
            if (H.search(sum) == true) 
            {
                print(sum, X[i], X[j])
                tripletFound = true
            }
            else
                H.insert(X[j])
        }
    }
    if (tripletFound == false) 
        print("triplet with 0 sum does not exist")
}

Solution code C++

void findTripletSum(int X[], int n) 
{
    bool tripletFound = false;
    for (int i = 0; i < n - 1; i = i + 1) 
    {
        unordered_map<int, bool> H;
        for (int j = i + 1; j < n; j = j + 1) 
        {
            int sum = -(X[i] + X[j]);
            if (H.find(sum) != H.end()) 
            {
                cout << sum << " " << X[i] << " " << X[j] << endl;
                tripletFound = true;
            }
            else
                H.insert({X[j], true});
        }
    }
    if (tripletFound == false) 
        cout << "triplet with 0 sum does not exist" << endl;
}

Solution code Python

def findTripletSum(X, n):
    tripletFound = False
    for i in range(n - 1):
        H = {}
        for j in range(i + 1, n):
            sum = -(X[i] + X[j])
            if sum in H:
                print(sum, X[i], X[j])
                tripletFound = True
            else:
                H[X[j]] = True
    if not tripletFound:
        print("triplet with 0 sum does not exist")

Solution code Java

class Solution
{
    public void findTripletSum(int[] X, int n) 
    {
        boolean tripletFound = false;

        for (int i = 0; i < n - 1; i = i + 1) 
        {
            Map<Integer, Boolean> H = new HashMap<>();
            for (int j = i + 1; j < n; j = j + 1) 
            {
                int sum = -(X[i] + X[j]);
                if (H.containsKey(sum)) 
                {
                    System.out.println(sum + " " + X[i] + " " + X[j]);
                    tripletFound = true;
                } 
                else 
                    H.put(X[j], true);
            }
        }
        if (tripletFound == false)
            System.out.println("triplet with 0 sum does not exist");
    }
}

Solution analysis

We explore every unique pair using a nested loop and perform constant operations at each iteration. Note: The time complexity of searching and insertion operation on the hash table is O(1) average.

Total number of loop iteration = Total number of pairs = nC2 = n(n - 1)/2 = O(n^2). So time complexity = Count of loop iteration * O(1) = O(n^2) * O(1) = O(n^2)

From another perspective, total number of loop iteration = (n - 1) + (n - 2)... + 1 = Sum of number from 1 to n - 1 = n(n - 1)/2 = O(n^2). We perform one hash table operation at each iteration: searching or insertion. So total hash table operations = Total number of loop iterations = O(n^2)

Space complexity is O(n) for storing values in the hash table.

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 similar to finding pair sum problem.

The idea is first to sort the array and traverse it from left to right. Now for each element X[i], we use two pointers l and r, to find out pairs (X[l], X[r]) with sum equal to -X[i] in the remaining part of the array from i + 1 to n - 1.

In other words, starting from every element X[i], we use a bi-directional two-pointer loop in the remaining part of the array to find out if there are any triplets (X[i], X[l], X[r]) with sum equal to zero or not.

Solution steps

Step 1: We sort the array in increasing order. Suppose we use an efficient O(nlogn) sorting algorithm like heap or quick sort.

Step 2: We traverse the array using a loop from i = 0 to n - 3. At each iteration of the outer loop: We initialize two pointers l = i + 1 and r = n - 1 and run a two-pointer loop until r > l. 

Step 3: Inside the inner loop: 

• We calculate sum = X[i] + X[l] + X[r].
• If (sum > 0), we decrement pointer r by 1, i.e. because array is sorted, so we move the right pointer to get the smaller sum value.
• If (sum < 0), we increment pointer l by 1 i.e. we move left pointer to get the larger sum value.
• If (sum = 0), we have found a zero sum triplet. So we print all three elements X[i], X[l] and X[r]. We also increment l by 1 and decrement r by 1 to find other triplets in the remaining part of the array.

Solution code C++

void findTripletSum(int X[], int n) 
{
    sort(X, X + n);
    bool tripletFound = false;
    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 (sum > 0)
                r = r - 1;
            else if (sum < 0)
                l = l + 1;
            else
            {                                   
                cout << X[i] << " " << X[l] << " " << X[r] << endl;
                tripletFound = true;
                l = l + 1;
                r = r - 1;
            }
        }
    }
    if (tripletFound == false) 
        cout << "triplet with 0 sum does not exist" << endl;
}

Solution code Python

def findTripletSum(X, n):
    X.sort()
    tripletFound = False
    for i in range(n - 2):
        l, r = i + 1, n - 1
        while r > l:
            sum = X[i] + X[l] + X[r]
            if sum > 0:
                r = r - 1
            elif sum < 0:
                l = l + 1
            else:
                print(X[i], X[l], X[r])
                tripletFound = True
                l = l + 1
                r = r - 1
    if not tripletFound:
        print("triplet with 0 sum does not exist")

Time and space complexity analysis

We are using two nested loops and doing a constant number of operations at each iteration. So time complexity of nested loop = O(n²). Let's try to analyse the loop precisely.

The outer loop runs n - 2 times, and in every iteration of outer loop, we run a two-pointer loop. Inside the two-pointer while loop, we are doing constant operations and moving pointer l or pointer r by or both by 1.

• The total number of loop iterations by while loop in the worst case = Length of the array from i + 1 to n - 1 = n - i - 1
• The total number of nested loop iterations = sum of (n - i - 1) for i = 0 to n - 2 = (n - 1) + (n - 2) + .... + 1 = n(n - 1)/2 = O(n^2).

So overall time complexity = Time complexity of sorting + Time complexity of nested loop = O(nlogn) + Count of nested loop iterations * O(1) = O(nlogn) + O(n^2) = O(n^2).

We use constant extra space inside the nested loop, So space complexity depends on the space complexity of the sorting algorithm. Space complexity = O(1) if we use heap sort and O(n) if we use merge sort.

Critical ideas to think!

• How can we modify the above approaches to find all triplets smaller than a given value or equal to a given value?
• Do the above approaches work fine if duplicate values are allowed?
• How can we modify the above approaches to return a list of all triplets rather than printing it?
• In the hash table approach, why are we inserting X[j] into the hash table when H.search(sum) == false? Can we think of implementing this approach by defining the hash function outside the nested loop?
• Can we think to solve this problem by sorting and applying the idea of binary search?

Suggested coding questions to practice

• Given array X[] of n integers, return an array of all the unique quadruplets such that: X[i] + X[j] + X[k] + X[l] == target.
• Given array X[] of n integers, return the number of distinct quadruplets such that: X[i] + X[j] + X[k] = X[l] and i < j < k < l.
• Given array X[] of n integers and an integer target, return indices of the two numbers such that they add up to the target.
• Given n numbers with no duplicates, count the number of unique triplets such that their XOR is 0.

Enjoy learning, Enjoy algorithms!