Problem Statement: Given an array of N integers, your task is to find unique triplets that add up to give a sum of zero. In short, you need to return an array of all the unique triplets [arr[a], arr[b], arr[c]] such that i!=j, j!=k, k!=i, and their sum is equal to zero.
Examples:
Example 1: Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]] Explanation: Out of all possible unique triplets possible, [-1,-1,2] and [-1,0,1] satisfy the condition of summing up to zero with i!=j!=k Example 2: Input: nums=[-1,0,1,0] Output: Output: [[-1,0,1],[-1,1,0]] Explanation: Out of all possible unique triplets possible, [-1,0,1] and [-1,1,0] satisfy the condition of summing up to zero with i!=j!=k
Solution:
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Solution 1 (Brute Force):
Intuition: While starting out, our aim must be to come up with a working solution first. Thus, given the problem, the most intuitive solution would be using three-pointers and checking for each possible triplet, whether we can satisfy the condition or not.
Approach: We keep three-pointers i,j, and k. For every triplet we find the sum of A[i]+A[j]+A[k]. If this sum is equal to zero, we’ve found one of the triplets. We add it to our data structure and continue with the rest.
Code:
C++ Code
#include<bits/stdc++.h>
using namespace std;
vector < vector < int >> threeSum(vector < int > & nums) {
vector < vector < int >> ans;
vector < int > temp;
int i, j, k;
for (i = 0; i < nums.size() - 2; i++) {
for (j = i + 1; j < nums.size() - 1; j++) {
for (k = j + 1; k < nums.size(); k++) {
temp.clear();
if (nums[i] + nums[j] + nums[k] == 0) {
temp.push_back(nums[i]);
temp.push_back(nums[j]);
temp.push_back(nums[k]);
}
if (temp.size() != 0)
ans.push_back(temp);
}
}
}
return ans;
}
int main() {
vector < int > arr { -1, 0, 1, 2, -1, -4};
vector < vector < int >> ans;
ans = threeSum(arr);
cout << "The triplets are as follows: " << endl;
for (int i = 0; i < ans.size(); i++) {
for (int j = 0; j < ans[i].size(); j++) {
cout << ans[i][j] << " ";
}
cout << endl;
}
return 0;
}Output:
The triplets are as follows:
-1 0 1
-1 2 -1
0 1 -1
Time Complexity : O(n^3) // 3 loops
Space Complexity : O(3*k) // k is the no.of triplets
Java Code
import java.util.*;
class TUF {
static ArrayList < ArrayList < Integer >> threeSum(int nums[]) {
ArrayList < ArrayList < Integer >> ans = new ArrayList < > ();
int i, j, k;
for (i = 0; i < nums.length - 2; i++) {
for (j = i + 1; j < nums.length - 1; j++) {
for (k = j + 1; k < nums.length; k++) {
ArrayList < Integer > temp = new ArrayList < > ();
if (nums[i] + nums[j] + nums[k] == 0) {
temp.add(nums[i]);
temp.add(nums[j]);
temp.add(nums[k]);
}
if (temp.size() != 0)
ans.add(temp);
}
}
}
return ans;
}
public static void main(String args[]) {
int arr[]={-1,0,1,2,-1,-4};
ArrayList < ArrayList < Integer >> ans;
ans = threeSum(arr);
System.out.println("The triplets are as follows: ");
for (int i = 0; i < ans.size(); i++) {
for (int j = 0; j < ans.get(i).size(); j++) {
System.out.print(ans.get(i).get(j) + " ");
}
System.out.println();
}
}
}Output:
The triplets are as follows:
-1 0 1
-1 2 -1
0 1 -1
Time Complexity : O(n^3) // 3 loops
Space Complexity : O(3*k) // k is the no.of triplets
Python Code
from typing import List
def threeSum(nums: List[int]) -> List[List[int]]:
ans = []
temp = []
for i in range(len(nums) - 2):
for j in range(i + 1, len(nums) - 1):
for k in range(j + 1, len(nums)):
temp = []
if nums[i] + nums[j] + nums[k] == 0:
temp.append(nums[i])
temp.append(nums[j])
temp.append(nums[k])
if len(temp) != 0:
ans.append(temp)
return ans
if __name__ == "__main__":
arr = [-1, 0, 1, 2, -1, -4]
ans = threeSum(arr)
print("The triplets are as follows: ")
for i in range(len(ans)):
for j in range(len(ans[i])):
print(ans[i][j], end=" ")
print()Output:
The triplets are as follows:
-1 0 1
-1 2 -1
0 1 -1
Time Complexity : O(n^3) // 3 loops
Space Complexity : O(3*k) // k is the no.of triplets
Solution 2 (Optimized Approach):
Intuition: Can we do something better?
I think yes! In our intuitive approach, we were considering all possible triplets. But do we really need to do that? I say we fixed two pointers i and j and came out with a combination of [-1,1,1] which doesn’t satisfy our condition. However, we still check for the next combination of say [-1,1,2] which is worthless. (Assuming the k pointer was pointing to 2).
Approach:
We could make use of the fact that we just need to return the triplets and thus could possibly sort the array. This would help us use a modified two-pointer approach to this problem.
Eg) Input : [-1,0,1,2,-1,-4]
After sorting, our array is : [-4,-1,-1,0,1,2]
Notice, that we are fixing the i pointer and then applying the traditional 2 pointer approach to check whether the sum of three numbers equals zero. If the sum is less than zero, it indicates our sum is probably too less and we need to increment our j pointer to get a larger sum. On the other hand, if our sum is more than zero, it indicates our sum is probably too large and we need to decrement the k pointer to reduce the sum and bring it closer to zero.
Code:
C++ Code
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> threeSum(vector<int>& num) {
vector<vector<int>> res;
sort(num.begin(), num.end());
// moves for a
for (int i = 0; i < (int)(num.size())-2; i++) {
if (i == 0 || (i > 0 && num[i] != num[i-1])) {
int lo = i+1, hi = (int)(num.size())-1, sum = 0 - num[i];
while (lo < hi) {
if (num[lo] + num[hi] == sum) {
vector<int> temp;
temp.push_back(num[i]);
temp.push_back(num[lo]);
temp.push_back(num[hi]);
res.push_back(temp);
while (lo < hi && num[lo] == num[lo+1]) lo++;
while (lo < hi && num[hi] == num[hi-1]) hi--;
lo++; hi--;
}
else if (num[lo] + num[hi] < sum) lo++;
else hi--;
}
}
}
return res;
}
int main() {
vector < int > arr{-1,0,1,2,-1,-4};
vector < vector < int >> ans;
ans = threeSum(arr);
cout << "The triplets are as follows: "<< endl;
for (int i = 0; i < ans.size(); i++) {
for (int j = 0; j < ans[i].size(); j++) {
cout << ans[i][j] <<" ";
}
cout << endl;
}
return 0;
}Output:
The triplets are as follows:
-1 -1 2
-1 0 1
Time Complexity : O(n^2)
Space Complexity : O(3*k) // k is the no.of triplets.
Java Code
import java.util.*;
class TUF {
static ArrayList < ArrayList < Integer >> threeSum(int[] num) {
Arrays.sort(num);
ArrayList < ArrayList < Integer >> res = new ArrayList < > ();
for (int i = 0; i < num.length - 2; i++) {
if (i == 0 || (i > 0 && num[i] != num[i - 1])) {
int lo = i + 1, hi = num.length - 1, sum = 0 - num[i];
while (lo < hi) {
if (num[lo] + num[hi] == sum) {
ArrayList < Integer > temp = new ArrayList < > ();
temp.add(num[i]);
temp.add(num[lo]);
temp.add(num[hi]);
res.add(temp);
while (lo < hi && num[lo] == num[lo + 1]) lo++;
while (lo < hi && num[hi] == num[hi - 1]) hi--;
lo++;
hi--;
} else if (num[lo] + num[hi] < sum) lo++;
else hi--;
}
}
}
return res;
}
public static void main(String args[]) {
int arr[]={-1,0,1,2,-1,-4};
ArrayList < ArrayList < Integer >> ans;
ans = threeSum(arr);
System.out.println("The triplets are as follows: ");
for (int i = 0; i < ans.size(); i++) {
for (int j = 0; j < ans.get(i).size(); j++) {
System.out.print(ans.get(i).get(j) + " ");
}
System.out.println();
}
}
}Output:
The triplets are as follows:
-1 -1 2
-1 0 1
Time Complexity : O(N^2)
Space Complexity : O(3*k) // k is the no.of triplets
Python Code
from typing import List
def threeSum(nums: List[int]) -> List[List[int]]:
res: List[List[int]] = []
temp: List[int] = []
nums.sort()
# moves for a
for i in range(len(nums) - 2):
if i == 0 or (i > 0 and nums[i] != nums[i - 1]):
lo = i + 1
hi = len(nums) - 1
sum = 0 - nums[i]
while lo < hi:
if nums[lo] + nums[hi] == sum:
temp = []
temp.append(nums[i])
temp.append(nums[lo])
temp.append(nums[hi])
res.append(temp)
while lo < hi and nums[lo] == nums[lo + 1]:
lo += 1
while lo < hi and nums[hi] == nums[hi - 1]:
hi -= 1
lo += 1
hi -= 1
elif nums[lo] + nums[hi] < sum:
lo += 1
else:
hi -= 1
return res
if __name__ == "__main__":
arr = [-1, 0, 1, 2, -1, -4]
ans = threeSum(arr)
print("The triplets are as follows: ")
for i in range(len(ans)):
for j in range(len(ans[i])):
print(ans[i][j], end=" ")
print()Output:
The triplets are as follows:
-1 -1 2
-1 0 1
Time Complexity : O(n^2)
Space Complexity : O(3*k) // k is the no.of triplets.
Special thanks to Naman Daga and Sudip Ghosh for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article