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] or [-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] or [-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 initialise 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 pseudocode
findTripletSum(X, n)
tripletFound = false
// Check every combination of three distinct elements
for i from 0 to n - 3
for j from i + 1 to n - 2
for k from j + 1 to n - 1
// Print the triplet if its sum is zero
if X[i] + X[j] + X[k] == 0
print X[i], X[j], X[k]
tripletFound = true
// Report if no triplet with a zero sum was found
if tripletFound == false
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).
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 initialise 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
findTripletSum(X, n)
tripletFound = false
// Fix each element as the first element of a triplet
for i from 0 to n - 2
H = empty hash set
// Search for two elements that complete a zero-sum triplet
for j from i + 1 to n - 1
requiredValue = -(X[i] + X[j])
if H contains requiredValue
print requiredValue, X[i], X[j]
tripletFound = true
else
H.insert(X[j])
// Report if no zero-sum triplet was found
if tripletFound == false
print "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 optimised 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 sort or quicksort.
Step 2: We traverse the array using a loop from i = 0 to n - 3. At each iteration of the outer loop, we initialise 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 the array is sorted, we move the right pointer to get a smaller sum value.
- If (sum < 0), we increment pointer l by 1, i.e. we move the left pointer to get a 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 pseudocode
findTripletSum(X, n)
sort X in ascending order
tripletFound = false
// Fix the first element of each possible triplet
for i from 0 to n - 3
l = i + 1
r = n - 1
// Search for the other two elements using two pointers
while l < r
sum = X[i] + X[l] + X[r]
if sum > 0
r = r - 1
else if sum < 0
l = l + 1
else
print X[i], X[l], X[r]
tripletFound = true
l = l + 1
r = r - 1
// Report if no zero-sum triplet was found
if tripletFound == false
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!