Find triplets with zero sum

Posted on ju. 21 octubre 2021 in Geeks for Geeks • 5 min read

Table of Contents:

Problem statement
Constraints
Explanation
Solution
Final thoughts

Problem statement

Here is the problem statement.

Constraints

$1 \le n \le 10^4$
$-10^6 \le A_i \le 10^6$

Expected Time Complexity: $\mathcal{O}\left(n^2\right)$
Expected Auxiliary Space: $\mathcal{O}(1)$

Explanation

Brute Force Approach

A naive approach to solve this problem would be to consider all the triplets present in the array and check if any of them sums up to zero.

Below is the implementation in pseudocode of the above approach:

for i = 0 to n - 1 do
    for j = i + 1 to n - 1 do
        for k = j + 1 to n - 1 A do
            if A[i] + A[j] + A[k] = 0 then
                return true
return false

Time complexity: $\mathcal{O}\left(n^3\right)$
Because those three nested loops are required.
Auxiliary space: $\mathcal{O}(1)$
No extra space required.
Final verdict: not a valid solution due to our constraints.

Hashing Approach

Now it's time for a question: do we really need to check all the triplets?, of course not! (otherwise this interview question would be meaningless 😂). A second approach is due to if $x + y + z = 0$ then $x = -y - z$. So we just need to find a triplet where the first number is the opposite of the sum of second and third number. We could do this using almost eny kind of hashing data structure.

Below is the implementation in pseudocode of the above approach:

H <- hash_map
for i = 0 to n - 1 do
    for j = i + 1 to n - 1 do
        if H.contains(-A[i] - A[j]) then
            return true
    H.insert(A[ i ])
return false

Time complexity: $\mathcal{O}\left(n^2\right)$
Because those two nested loops are required and time complexity for checking if a value exists in a hash map is $\mathcal{O}(1)$.
Auxiliary space: $\mathcal{O}(n)$
Because at the end the hash map will contain $n$ elements.
Final verdict: not a valid solution due to our constraints.

Two Pointers Approach

Another approach, and our final approach, is sorting the array $A$ and then try to find a triplet $(i, j, k)$ such that $0 \le i \lt j \lt k \lt n$ and $A_i + A_j + A_k = 0$. Given any triplet $(i, j, k)$ such that $0 \le i \lt j \lt k \lt n$ then there are just $3$ options we need to check.

$$A_i + A_j + A_k \left\{\begin{array}{cl} = 0 & \text{We found a solution!}\\ \lt 0 & \text{Then } A_i + A_j + A_k \le A_i + A_{j+1} + A_k\\ \gt 0 & \text{Then } A_i + A_j + A_k \ge A_i + A_j + A_{k-1} \end{array}\right.$$

Following the above idea, we could iterate through every $0 \le i \lt n$ and search for a valid pair of $(j, k)$ in the range $[i+1,n-1]$.

Demonstration

If there is no sulution, it's pretty obviuos that we don't find a solution, because we check the sum of $3$ numbers and it will never be $0$.

Let's assume there exists a triplet $(i, j, k)$ such that $0 \le i \lt j \lt k \lt n$ and $A_i + A_j + A_k = 0$. It is obviuos that our algorithm will reach $i$ after some steps (maybe none). After that, it is also straightforward to see that we will reach either $j$ or $k$, because we iterate through every $i \lt v \lt n$ and $i \lt j,k$.

Suppose we reach $j$ before $k$, then with the right pointer we are at position $k \lt p \lt n$ and $\forall p: k \lt p \lt n \implies A_i + A_j + A_p \ge 0$ because $A_i + A_j + A_k = 0$ and $A_k \le A_p$ given that the array is sorted.
So either we found another valid solution with triplet $(i, j, p)$ or we have to decrease our right pointer until we reach $k$ or another valid solution.
Suppose we reach $k$ before $j$, then with the left pointer we are at position $i \lt p \lt j$ and $\forall p: i \lt p \lt j \implies A_i + A_p + A_k \le 0$ because $A_i + A_j + A_k = 0$ and $A_p \le A_j$ given that the array is sorted.
So either we found another valid solution with triplet $(i, p, k)$ or we have to increase our left pointer until we reach $j$ or another valid solution.

Solution

Here is the solution code of this problem in multiple languages.

int comparer(const void* a, const void* b)
{
    int int_a = *((int*)a);
    int int_b = *((int*)b);
    if(int_a == int_b) return 0;
    return int_a < int_b ? -1 : 1;
}

int findTriplets(int array[], int n)
{
    qsort(array, n, sizeof(int), comparer);
    for(int i = 0 ; i < n ; ++i){
        int left = i + 1, right = n - 1;
        while(left < right){
            int sum = array[ i ] + array[ left ] + array[ right ];
            if(sum == 0)
                return 1;
            else if(sum < 0)
                ++left;
            else
                --right;
        }
    }
    return 0;
}

class Solution{
  public:
    bool findTriplets(int array[], int n)
    { 
        sort(array, array + n);
        for(int i = 0 ; i < n ; ++i){
            int left = i + 1, right = n - 1;
            while(left < right){
                int sum = array[ i ] + array[ left ] + array[ right ];
                if(sum == 0)
                    return true;
                else if(sum < 0)
                    ++left;
                else
                    --right;
            }
        }
        return false;
    }
};

class Solution
{
    public bool findTriplets(int[] array, int n)
    {
        Array.Sort(array);
        for(int i = 0 ; i < n ; ++i){
            int left = i + 1, right = n - 1;
            while(left < right){
                int sum = array[ i ] + array[ left ] + array[ right ];
                if(sum == 0)
                    return true;
                else if(sum < 0)
                    ++left;
                else
                    --right;
            }
        }
        return false;
    }
}

class Solution:   
    def findTriplets(self, array, n):
        array.sort()
        for i in range(n):
            left, right = i + 1, n - 1
            while left < right:
                sum_ = array[ i ] + array[ left ] + array[ right ]
                if sum_ == 0:
                    return True
                elif sum_ < 0:
                    left += 1
                else:
                    right -= 1
        return False

class Solution
{
    public boolean findTriplets(int array[] , int n)
    {
        Arrays.sort(array);
        for(int i = 0 ; i < n ; ++i){
            int left = i + 1, right = n - 1;
            while(left < right){
                int sum = array[ i ] + array[ left ] + array[ right ];
                if(sum == 0)
                    return true;
                else if(sum < 0)
                    ++left;
                else
                    --right;
            }
        }
        return false;
    }
}

class Solution {
    findTriplets(array, n)
    {
        array.sort(function(a, b){ return a - b });
        for(let i = 0 ; i < n ; ++i){
            let left = i + 1, right = n - 1;
            while(left < right){
                let sum = array[ i ] + array[ left ] + array[ right ];
                if(sum === 0)
                    return true;
                else if(sum < 0)
                    ++left;
                else
                    --right;
            }
        }
        return false;
    }
}

Time complexity: $\mathcal{O}\left(n^2\right)$
Because those two nested loops are required and all internal operations are $\mathcal{O}(1)$.
Auxiliary space: $\mathcal{O}(1)$
No extra space needed.
Final verdict: valid solution!

Final thoughts

This is a pretty simple and easy problem to understand two pointers approach.