Problem Statement
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that:
i,j, andkare distinct indices.nums[i] + nums[j] + nums[k] == 0.
Note:
- The solution set must not contain duplicate triplets.
- The output can be returned in any order.
LeetCode:
Examples
Example 1:
Input: nums = [-1, 0, 1, 2, -1, -4]
Output: [ [-1, 0, 1], [-1, -1, 2] ]
Explanation:
nums[0] + nums[1] + nums[2] = 0
-1 + 0 + 1 = 0
nums[0] + nums[5] + nums[4] = 0
-1 + -1 + 2 = 0Example 2:
Input: nums = [2, -2, 0, 3, -3, 5]
Output: [ [-2, 0, 2], [-3, -2, 5], [-3, 0, 3] ]
Explanation:
nums[1] + nums[2] + nums[0] = 0
nums[4] + nums[1] + nums[5] = 0
nums[4] + nums[2] + nums[3] = 0Example 3:
Input: nums = [2, -1, -1, 3, -1]
Output: [[-1, -1, 2]]
Explanation:
nums[1] + nums[2] + nums[0] = 0
Note that we have used two -1s as they are separate elements with different indexes
But we have not used the -1 at index 4 as that would create a duplicate tripletExample 4:
Input: nums = [0, 1, 1]
Output: []
Explanation:
No triplets sum to zero.Problem Understanding:
The Three Sum Zero problem requires finding all unique triplets in an array whose sum is zero.
Example Explanation:
In the given example, the array [-1, 0, 1, 2, -1, -4] has two unique triplets that add up to zero. [-1, 0, 1] and [-1, -1, 2]. These triplets are the subsets of the array whose elements, when summed, result in zero.
Different Approaches to Solve:
1️⃣ Brute Force:
A brute-force approach involves using three nested loops to check every triplet in the array. This approach has a time complexity of O(n^3) and is not the most efficient for large arrays.
The most naive idea is to check all possible triplets using 3 loops and among them, consider the ones whose sum is equal to the given target 0.
Before taking them as the answer, sort the triplets in ascending order so as to consider only the unique triplets.
Approach
- Declare a set data structure for storing the unique triplets.
- Used nested looping structure to traverse the array, and take triplets into account.
- First loop will run from 0th index till the length of array, lets call it i. Inside it, there will be the another loop(say j) that will run from i+1 to n-1. Then a third loop(say k) that runs from j+1 to n-1.
- Now, inside these 3 nested loops, check the sum of arr[i] and arr[j] and arr[k], and if it is equal to the target i.e. 0 sort this triplet and insert it in the set data structure. Finally, return the list of triplets stored in the set data structure.
Dry Run:
initialization:
+-----+-----+-----+-----+-----+-----+
nums = | -1 | 0 | 1 | 2 | -1 | -4 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^ ^ ^
| | |
i j k
+--------------+
set = | empty |
+--------------+i = 0, j = 1, k = 2
+-----+-----+-----+-----+-----+-----+
nums = | -1 | 0 | 1 | 2 | -1 | -4 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^ ^ ^
| | |
i j k
+--------------+
set = | empty |
+--------------+
if (arr[i] + arr[j] + arr[k] == 0)
arr[0] + arr[1] + arr[2] == 0
-1 + 0 + 1 == 0
True
Create a temp vector of i, j, k which would
be [-1, 0, 1]
Sort temp vector, { why? without sorting
the trplets [-1, 0, 1] and
[0, -1, 1] would be
treated as different
triplets, even though they
contain the same elements.
By sorting the triplet,
both [-1, 0, 1] and
[0, -1, 1] become
[-1, 0, 1] and thus
recognized as the same
triplet.
}
Insert the temp vector into the set.
k++i = 0, j = 1, k = 2
+-----+-----+-----+-----+-----+-----+
nums = | -1 | 0 | 1 | 2 | -1 | -4 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^ ^ ^
| | |
i j k
+--------------+
set = | [-1, 0, 1] |
+--------------+
if (arr[i] + arr[j] + arr[k] == 0)
arr[0] + arr[1] + arr[3] == 0
-1 + 0 + 2 == 0
False
k++i = 0, j = 1, k = 4
+-----+-----+-----+-----+-----+-----+
nums = | -1 | 0 | 1 | 2 | -1 | -4 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^ ^ ^
| | |
i j k
+--------------+
set = | [-1, 0, 1] |
+--------------+
if (arr[i] + arr[j] + arr[k] == 0)
arr[0] + arr[1] + arr[4] == 0
-1 + 0 + 1 == 0
True
Create a temp vector of i, j, k which would
be [-1, 0, 1]
Sort temp vector
Insert the temp vector into the set {since
this triplet already present in the set, it
won't be inserted.}
k++i = 0, k = 1, j = 5
+-----+-----+-----+-----+-----+-----+
nums = | -1 | 0 | 1 | 2 | -1 | -4 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^ ^ ^
| | |
i j k
+--------------+
set = | [-1, 0, 1] |
+--------------+
if (arr[i] + arr[j] + arr[k] == 0)
arr[0] + arr[1] + arr[4] == 0
-1 + 0 + -4 == 0
False
Since incrementing k, would go out of the arrays
bounds so, terminate this most inside loop and
increment j, and reset k to j + 1.i = 0, j = 2, k = 3
+-----+-----+-----+-----+-----+-----+
nums = | -1 | 0 | 1 | 2 | -1 | -4 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^ ^ ^
| | |
i j k
+--------------+
set = | [-1, 0, 1] |
+--------------+
if (arr[i] + arr[j] + arr[k] == 0)
arr[0] + arr[2] + arr[3] == 0
-1 + 1 + 2 == 0
False
k++i = 0, k = 2, j = 4
+-----+-----+-----+-----+-----+-----+
nums = | -1 | 0 | 1 | 2 | -1 | -4 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^ ^ ^
| | |
i j k
+--------------+
set = | [-1, 0, 1] |
+--------------+
if (arr[i] + arr[j] + arr[k] == 0)
arr[0] + arr[2] + arr[4] == 0
-1 + 1 + -1 == 0
False
k++i = 0, j = 2, k = 5
+-----+-----+-----+-----+-----+-----+
nums = | -1 | 0 | 1 | 2 | -1 | -4 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^ ^ ^
| | |
i j k
+--------------+
set = | [-1, 0, 1] |
+--------------+
if (arr[i] + arr[j] + arr[k] == 0)
arr[0] + arr[2] + arr[5] == 0
-1 + 1 + -4 == 0
False
Since incrementing k, would go out of the arrays
bounds so, terminate this most inside loop and
increment j, and reset k to j + 1.i = 0, j = 3, k =4
+-----+-----+-----+-----+-----+-----+
nums = | -1 | 0 | 1 | 2 | -1 | -4 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^ ^ ^
| | |
i j k
+--------------+
set = | [-1, 0, 1] |
+--------------+
if (arr[i] + arr[j] + arr[k] == 0)
arr[0] + arr[3] + arr[4] == 0
-1 + 2 + -1 == 0
True
Create a temp vector of i, j, k which would
be [-1, 2, -1]
Sort temp vector, { why? without sorting
the trplets [-1, 2, -1] and
[-1, -1, 2] would be
treated as different
triplets, even though they
contain the same elements.
By sorting the triplet,
both [-1, 2, -1] and
[-1, -1, 2] become
[-1, -1, 2] and thus
recognized as the same
triplet.
}
Insert the temp vector into the set.
k++i = 0, j = 3, k = 5
+-----+-----+-----+-----+-----+-----+
nums = | -1 | 0 | 1 | 2 | -1 | -4 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^ ^ ^
| | |
i j k
+--------------+---------------+
set = | [-1, 0, 1] | [-1, -1, 2] |
+--------------+---------------+
if (arr[i] + arr[j] + arr[k] == 0)
arr[0] + arr[3] + arr[5] == 0
-1 + 2 + -4 == 0
False
Since incrementing k, would go out of the arrays
bounds so, terminate this most inside loop and
increment j, and reset k to j + 1.Continue
Keep doing this process
For i = 0 to n-3
For j = i + 1 to n-2
For k = j + 1 to n-1Code:
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
//Function to find triplets having sum equals to target
vector<vector<int>> threeSum(vector<int>& nums) {
// Set to store unique triplets
set<vector<int>> tripletSet;
int n = nums.size();
// Check all possible triplets
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
for (int k = j + 1; k < n; k++) {
if (nums[i] + nums[j] + nums[k] == 0) {
// Found a triplet that sums up to target
vector<int> temp = {nums[i], nums[j], nums[k]};
/* Sort the triplet to ensure
uniqueness when storing in set*/
sort(temp.begin(), temp.end());
tripletSet.insert(temp);
}
}
}
}
// Convert set to vector (unique triplets)
vector<vector<int>> ans(tripletSet.begin(), tripletSet.end());
// OR
/*
for(auto itr: tripletSet) {
ans.push_back(itr);
}
*/
//Return the ans
return ans;
}
};
int main() {
vector<int> nums = {-1, 0, 1, 2, -1, -4};
// Create an instance of Solution class
Solution sol;
vector<vector<int>> ans = sol.threeSum(nums);
// Print the result
for (auto& triplet : ans) {
cout << "[";
for (auto& num : triplet) {
cout << num << " ";
}
cout << "] ";
}
cout << "\n";
return 0;
}
Complexity Analysis:
- Time Complexity:
O(N^3 x log(no. of unique triplets)), where N is size of the array. Using 3 nested loops & inserting triplets into the set takes O(log(no. of unique triplets)) time complexity. But we are not considering the time complexity of sorting as we are just sorting 3 elements every time. - Space Complexity:
O(2 x no. of the unique triplets)for using a set data structure and a list to store the triplets.
2️⃣ Better Approach
Intuition:
The better approach uses simple mathematics where some calculative parameter is taken in RHS(right hand side) to compute the result.
For example if a + b + c = 0, then a + b = -c. Similar idea is used here.
Approach:
- Declare a set data structure to store unique triplets. Then iterate in the array lets call the variable i from index 0 to n -1. Inside it, there will be the second loop(say j) that will run from i+1 to n-1.
- Declare another HashSet to store the array elements as we intend to search for the third element using this HashSet.
- Inside the nested loop, calculate the value of the third element i.e. -(arr[i]+arr[j]).
- If the third element exists in the HashSet, sort these 3 values i.e. arr[i], arr[j], and the third element, and insert it in the set data structure declared in step 1.
- After that, insert the j-th element i.e. arr[j] in the HashSet as we only want to insert those array elements that are in between indices i and j. Finally, return a list of triplets stored in the set data structure.
Dry Run:
Initialization
+-----+-----+-----+-----+-----+-----+
arr = | -1 | 0 | 1 | 2 | -1 | -4 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^ ^
| |
i j
+--------------+
Result set = | empty |
+--------------+
i = 0, j = 1
+-----+-----+-----+-----+-----+-----+
arr = | -1 | 0 | 1 | 2 | -1 | -4 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^ ^
| |
i j
+--------------+
Result set = | empty |
+--------------+
+--------------+
tempHashSet = | empty |
+--------------+
third = - (arr[i] + arr[j])
third = - (-1 + 0)
third = 1
Does hashSet contains third which is 1.
False
Add 1 to hashSet
j++i = 0, j = 1
+-----+-----+-----+-----+-----+-----+
arr = | -1 | 0 | 1 | 2 | -1 | -4 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^ ^
| |
i j
+--------------+
Result set = | empty |
+--------------+
+-----+
tempHashSet = | 1 |
+-----+
third = - (arr[i] + arr[j])
third = - (-1 + 1)
third = 0
Does hashSet contains third which is 0.
False
Add 0 to hashSet
j++i = 0, j = 2
+-----+-----+-----+-----+-----+-----+
arr = | -1 | 0 | 1 | 2 | -1 | -4 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^ ^
| |
i j
+--------------+
Result set = | empty |
+--------------+
+-----+-----+
tempHashSet = | 1 | 0 |
+-----+-----+
third = - (arr[i] + arr[j])
third = - (-1 + 2)
third = 1
Does hashSet contains third which is 1.
True
Create temp vector {arr[i], arr[j], third}
Sort the temp vector
Insert the vector into the resultSet
j++i = 0, j = 3
+-----+-----+-----+-----+-----+-----+
arr = | -1 | 0 | 1 | 2 | -1 | -4 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^ ^
| |
i j
+--------------+
Result set = | (-1, 1, 2) |
+--------------+
+-----+-----+
tempHashSet = | 1 | 0 |
+-----+-----+
third = - (arr[i] + arr[j])
third = - (-1 + (-1))
third = - (-1 - 1)
third = - (-2)
third = 2
Does hashSet contains third which is 2.
False
Add 2 to hashSet
j++Continue
Keep doing this process
For i = 0 to n-1
For j = i + 1 to nCode:
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Function to find triplets having sum equals to target
vector<vector<int>> threeSum(vector<int>& nums) {
// Set to store unique triplets
set<vector<int>> tripletSet;
int n = nums.size();
// Check all possible triplets
for (int i = 0; i < n; i++) {
// Set to store elements seen so far in the loop
set<int> hashset;
for (int j = i + 1; j < n; j++) {
// Calculate the 3rd element needed to reach target
int third = - (nums[i] + nums[j]);
/* Find if third element exists in
hashset (complements seen so far)*/
if (hashset.find(third) != hashset.end()) {
// Found a triplet that sums up to target
vector<int> temp = {nums[i], nums[j], third};
/* Sort the triplet to ensure
uniqueness when storing in set*/
sort(temp.begin(), temp.end());
tripletSet.insert(temp);
}
/* Insert the current element
into hashset for future checks*/
hashset.insert(nums[j]);
}
}
// Convert set to vector (unique triplets)
vector<vector<int>> ans(tripletSet.begin(), tripletSet.end());
//Return the ans
return ans;
}
};
int main() {
vector<int> nums = {-1, 0, 1, 2, -1, -4};
// Create an instance of Solution class
Solution sol;
vector<vector<int>> ans = sol.threeSum(nums);
// Print the result
for (auto& triplet : ans) {
cout << "[";
for (auto& num : triplet) {
cout << num << " ";
}
cout << "] ";
}
cout << "\n";
return 0;
}
3️⃣ Optimal Approach
Sorting + Two-Pointers:
Sort the array and use two pointers to find pairs that sum to the negative of the current element. This approach reduces the time complexity to O(n^2) due to sorting step.
Approach:
- Sort the entire array & iterate from 0 to n-1 in the array, lets call the loop variable i. In each iteration, this value will be fixed for all different values of the rest of the 2 pointers.
- Inside the loop, first check if the current and the previous element is the same and if it is, do nothing and continue to the next value of i.
- After that, there will be 2 moving pointers i.e. j(starts from i+1) and k(starts from the last index). The pointer j will move forward and the pointer k will move backward until they cross each other while the value of i will be fixed.
- Now check the sum of arr[i] and arr[j] and arr[k]. If the sum is exceeding target, then the ask is to use lesser valued elements and so decrease the value of k(i.e. k--). If the sum is lesser than the target, we need a bigger value and so increase the value of j (i.e. j++).
- If the sum is equal to the target, simply insert the triplet i.e. arr[i], arr[j], arr[k] into answer data structure and move the pointers j and k skipping the duplicate elements(i.e. by checking the adjacent elements while moving the pointers). Finally, return the list of unique triplets.
Dry Run:
Initialization
+-----+-----+-----+-----+-----+-----+
arr = | -1 | 0 | 1 | 2 | -1 | -4 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
Sort the arr
+-----+-----+-----+-----+-----+-----+
arr = | -4 | -1 | -1 | 0 | 1 | 2 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
Initialize the Loop
+-----+-----+-----+-----+-----+-----+
arr = | -4 | -1 | -1 | 0 | 1 | 2 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^ ^ ^
| | |
i j k
+--------------+
Result set = | |
+--------------+i = 0, j = 1, k = 5
+-----+-----+-----+-----+-----+-----+
arr = | -4 | -1 | -1 | 0 | 1 | 2 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^ ^ ^
| | |
i j k
i = 0
j = 1
k = 5
+--------------+
Result set = | |
+--------------+
sum = arr[i] + arr[j] + arr[k]
= -4 + (-1) + 2
= -4 - 1 + 2
= -5 + 2
= -3
Since sum is less than 0 increment the left pointer which is j.
Keep incrementing until arr[j] != arr[j - 1] && j < k
j++i = 0, j = 3, k = 5
+-----+-----+-----+-----+-----+-----+
arr = | -4 | -1 | -1 | 0 | 1 | 2 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^ ^ ^
| | |
i j k
i = 0
j = 3
k = 5
+--------------+
Result set = | |
+--------------+
sum = arr[i] + arr[j] + arr[k]
= -4 + 0 + 2
= -4 + 2
= -2
Since sum is less than 0 increment the left pointer which is j.
Keep incrementing until arr[j] != arr[j - 1] && j < k
j++i = 0, j = 4, k = 5
+-----+-----+-----+-----+-----+-----+
arr = | -4 | -1 | -1 | 0 | 1 | 2 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^ ^ ^
| | |
i j k
i = 0
j = 4
k = 5
+--------------+
Result set = | |
+--------------+
sum = arr[i] + arr[j] + arr[k]
= -4 + 1 + 2
= -4 + 3
= -1
Since sum is less than 0 increment the left pointer which is j.
Keep incrementing until arr[j] != arr[j - 1] && j < k
Now since j will become equal to k so break the internal loop.
and reset j, k to (i + 1) and (size() - 1) respectively.i = 1, j = 2, k = 5
+-----+-----+-----+-----+-----+-----+
arr = | -4 | -1 | -1 | 0 | 1 | 2 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^ ^ ^
| | |
i j k
i = 1
j = 2
k = 5
+--------------+
Result set = | |
+--------------+
sum = arr[i] + arr[j] + arr[k]
= -1 - 1 + 2
= 0
Push this combination into the result vector.
Increment j and decrement k.
Skip duplication by checking nums[j] != nums[j - 1]
nums[k] != nums[k + 1]Keep Doing until i < nums.size()
+-----+-----+-----+-----+-----+-----+
arr = | -4 | -1 | -1 | 0 | 1 | 2 |
+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^ ^ ^
| | |
i j k
i = 1
j = 2
k = 5
+--------------+
Result set = | |
+--------------+
sum = arr[i] + arr[j] + arr[k]
= -1 - 1 + 2
= 0
Push this combination into the result vector.
Increment j and decrement k.
Skip duplication by checking nums[j] != nums[j - 1]
nums[k] != nums[k + 1]
Code:
#include <iostream>
#include <vector>
#include <algorithm>
// Function to find all unique triplets that sum to zero using sorting and two pointers
std::vector<std::vector<int>> threeSumSorting(std::vector<int>& nums) {
std::vector<std::vector<int>> result; // Vector to store the triplets
int n = nums.size();
// Step 1: Sort the array to facilitate two-pointer approach and to handle duplicates
std::sort(nums.begin(), nums.end());
// Step 2: Traverse through each element, considering it as the first element of the triplet
for (int i = 0; i < n - 2; ++i) {
// Skip duplicate elements to avoid repeated triplets
if (i > 0 && nums[i] == nums[i - 1])
continue;
int left = i + 1; // Pointer to the next element
int right = n - 1; // Pointer to the last element
// Step 3: Use two pointers to find the other two elements of the triplet
while (left < right) {
int sum = nums[i] + nums[left] + nums[right]; // Calculate the sum of the triplet
if (sum == 0) { // If the sum is zero, we've found a valid triplet
result.push_back({nums[i], nums[left], nums[right]}); // Store the triplet
// Move the left pointer to the right, skipping duplicates
while (left < right && nums[left] == nums[left + 1])
++left;
// Move the right pointer to the left, skipping duplicates
while (left < right && nums[right] == nums[right - 1])
--right;
// Move both pointers to continue finding other triplets
++left;
--right;
} else if (sum < 0) { // If the sum is less than zero, move the left pointer to increase the sum
++left;
} else { // If the sum is greater than zero, move the right pointer to decrease the sum
--right;
}
}
}
return result; // Return the result containing all the valid triplets
}
int main() {
std::vector<int> nums = {-1, 0, 1, 2, -1, -4}; // Input array
std::vector<std::vector<int>> result = threeSumSorting(nums); // Call the function
// Print the result
std::cout << "Triplets with Zero Sum (Sorting + Two Pointers):\n";
for (const auto& triplet : result) { // Iterate through each triplet
std::cout << "[";
for (int num : triplet) { // Print the numbers in each triplet
std::cout << num << " ";
}
std::cout << "]\n";
}
return 0;
}
Complexity Analysis:
- Time Complexity:
O(n log n) + O(n^2), wherenis the size of the array.- As the pointer i, is running for approximately N times. And both the pointers j and k combined can run for approximately N times including the operation of skipping duplicates. So the total time complexity will be O(N^2).
- Space Complexity:
O(1), no extra space is needed.