3Sum: Find All Unique Triplets with Zero Sum

106.7k
0

In Three Sum, we are given an integer array nums.

We need to find all unique triplets such that the sum of the three values is equal to 0.

The three elements must come from three different indices. This means the same element cannot be used more than once in a triplet.

The answer should not contain duplicate triplets.

Example 1

Input: nums = [-1, 0, 1, 2, -1, -4]

Output: [[-1, -1, 2], [-1, 0, 1]]

Explanation: The triplets [-1, -1, 2] and [-1, 0, 1] have a sum equal to 0. These are the only unique triplets that satisfy the condition.

Example 2

Input: nums = [0, 1, 1]

Output: []

Explanation: No triplet exists whose sum is equal to 0.

Example 3

Input: nums = [0, 0, 0]

Output: [[0, 0, 0]]

Explanation: The triplet [0, 0, 0] has a sum equal to 0.

Brute Force Approach

The direct approach examines every possible combination of three different indices.

Maintaining first < second < third ensures that each index combination is generated once and prevents the same position from appearing multiple times inside one triplet.

However, duplicate values may still produce the same value triplet through different index combinations. Sorting each valid triplet gives it a consistent arrangement, while a set removes repeated answers.

Algorithm

  • Store the array size in n. If n < 3, return an empty answer because three different indices are required to form a triplet.

  • Create uniqueTriplets to store valid triplets without repeated value combinations.

  • Use first, second, and third such that first < second < third. This considers every combination of three different indices exactly once.

  • Calculate the sum of the three selected values to check whether the current combination satisfies the required total of 0.

  • If the sum is 0, sort the three values before inserting them into uniqueTriplets, so identical value triplets generated from different indices are treated as the same answer.

  • Copy the distinct triplets from uniqueTriplets into the answer and return it.

Dry Run

3 Sum Brute Force Dry Run.png

3 Sum Brute Force Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int n = nums.size();
// Three different indices are required.
if (n < 3) {
return {};
}
set<vector<int>> uniqueTriplets;
/*
* Check every combination of three
* different indices exactly once.
*/
for (int first = 0; first < n - 2; first++) {
for (int second = first + 1; second < n - 1; second++) {
for (int third = second + 1; third < n; third++) {
long long sum =
(long long) nums[first] +
nums[second] +
nums[third];
// A zero sum gives a valid triplet.
if (sum == 0) {
vector<int> triplet = {
nums[first],
nums[second],
nums[third]
};
/*
* Sorting gives duplicate triplets
* the same arrangement.
*/
sort(triplet.begin(), triplet.end());
uniqueTriplets.insert(triplet);
}
}
}
}
return vector<vector<int>>(
uniqueTriplets.begin(),
uniqueTriplets.end()
);
}
};
int main() {
vector<int> nums = {-1, 0, 1, 2, -1, -4};
Solution solution;
vector<vector<int>> answer = solution.threeSum(nums);
for (const auto& triplet : answer) {
for (int value : triplet) {
cout << value << " ";
}
cout << endl;
}
return 0;
}

Complexity Analysis

Time Complexity: O(N³), where N represents the array size. Three nested loops examine every possible index triplet. Sorting three values requires constant time.

Space Complexity: O(K), where K represents the number of unique triplets stored for duplicate removal. The returned answer may also contain K triplets.

Better Approach

After fixing two values, only one specific third value can make the total equal to 0.

For selected values nums[first] and nums[second], the required third value is:

thirdValue = -(nums[first] + nums[second])

A hash set stores values visited earlier during the current first traversal. This replaces the third loop with an average constant-time lookup.

A separate set of arranged triplets removes duplicate answers.

Algorithm

  • Store the array size in n. If fewer than three elements are available, return an empty answer.

  • Create uniqueTriplets to remove duplicate answers, and treat every index first as the fixed first element of a possible triplet.

  • For each first, create a fresh seenValues set so it contains only values visited during the current search for the remaining two elements.

  • Move second from first + 1 to the end and calculate thirdValue = -(nums[first] + nums[second]), which is the value needed to make the total equal to 0.

  • If thirdValue already exists in seenValues, arrange the three values in sorted order and insert the triplet into uniqueTriplets to avoid duplicate answers.

  • Insert nums[second] into seenValues after the lookup so the current index cannot be reused as the third element. Return all distinct triplets after the traversals finish.

Dry Run

3 Sum Better Dry Run.png

3 Sum Better Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int n = nums.size();
// Three different indices are required.
if (n < 3) {
return {};
}
set<vector<int>> uniqueTriplets;
for (int first = 0; first < n - 2; first++) {
unordered_set<long long> seenValues;
/*
* The set stores values already visited
* for the current fixed element.
*/
for (int second = first + 1; second < n; second++) {
long long thirdValue =
-(long long)(nums[first] + (long long)nums[second]);
/*
* An earlier matching value completes
* the required zero-sum triplet.
*/
if (seenValues.find(thirdValue) != seenValues.end()) {
vector<int> triplet = {
nums[first],
nums[second],
(int) thirdValue
};
sort(triplet.begin(), triplet.end());
uniqueTriplets.insert(triplet);
}
/*
* Insert after lookup so the current
* index cannot be reused.
*/
seenValues.insert(nums[second]);
}
}
return vector<vector<int>>(
uniqueTriplets.begin(),
uniqueTriplets.end()
);
}
};
int main() {
vector<int> nums = {-1, 0, 1, 2, -1, -4};
Solution solution;
vector<vector<int>> answer = solution.threeSum(nums);
for (const auto& triplet : answer) {
for (int value : triplet) {
cout << value << " ";
}
cout << endl;
}
return 0;
}

Complexity Analysis

Time Complexity: O(N²) on average, where N represents the array size. Two nested traversals process the index pairs, while hash-set lookup and insertion require average O(1) time.

Space Complexity: O(N + K), where seenValues may store O(N) values and uniqueTriplets may store K distinct triplets.

Optimal Approach

Replace your current duplicated block with this actual intuition:

Sorting the array allows the remaining two values to be searched efficiently after fixing one element.

For every fixed position, place left immediately after it and right at the end of the array. Because the values are sorted, the current sum tells us which pointer should move.

If the sum is smaller than 0, a larger value is required, so left moves forward. If the sum is greater than 0, a smaller value is required, so right moves backward.

When the sum becomes 0, the current three values form a valid triplet. Since equal values are adjacent after sorting, duplicate values at fixed, left, and right can be skipped directly instead of using an additional set.

Algorithm

  • Store the array size in n. If n < 3, return an empty answer. Sort nums so pointer movement and duplicate removal can be handled efficiently.

  • Traverse fixed from index 0 to n - 3. If fixed > 0 and nums[fixed] == nums[fixed - 1], skip the current position because the same fixed value has already been processed.

  • Initialize left = fixed + 1 and right = n - 1, representing the remaining two elements needed with nums[fixed].

  • Calculate the sum of nums[fixed], nums[left], and nums[right]. If the sum is negative, move left forward to increase it; if the sum is positive, move right backward to decrease it.

  • If the sum is 0, add the current triplet to the answer, move both pointers inward, and skip repeated values at left and right so the same triplet is not added again.

  • Return the answer after every fixed position and its corresponding two-pointer range have been processed.

Dry Run

3 Sum Optimal Dry Run.png

3 Sum Optimal Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int n = nums.size();
vector<vector<int>> answer;
// Three different indices are required.
if (n < 3) {
return answer;
}
sort(nums.begin(), nums.end());
for (int fixed = 0; fixed < n - 2; fixed++) {
/*
* Skip the same fixed value to avoid
* generating duplicate triplets.
*/
if (fixed > 0 && nums[fixed] == nums[fixed - 1]) {
continue;
}
int left = fixed + 1;
int right = n - 1;
while (left < right) {
long long sum =
(long long) nums[fixed] +
nums[left] +
nums[right];
// A smaller sum needs a larger left value.
if (sum < 0) {
left++;
}
// A larger sum needs a smaller right value.
else if (sum > 0) {
right--;
}
else {
answer.push_back({
nums[fixed],
nums[left],
nums[right]
});
left++;
right--;
/*
* Skip repeated values so the same
* triplet is not added again.
*/
while (left < right &&
nums[left] == nums[left - 1]) {
left++;
}
while (left < right &&
nums[right] == nums[right + 1]) {
right--;
}
}
}
}
return answer;
}
};
int main() {
vector<int> nums = {-1, 0, 1, 2, -1, -4};
Solution solution;
vector<vector<int>> answer = solution.threeSum(nums);
for (const auto& triplet : answer) {
for (int value : triplet) {
cout << value << " ";
}
cout << endl;
}
return 0;
}

Complexity Analysis

Time Complexity: O(N²), where N represents the array size. Sorting requires O(N log N) time, and a linear two-pointer traversal runs for every fixed index.

Space Complexity: O(1) explicit auxiliary space when the returned answer is excluded. Sorting may require implementation-dependent internal memory.

FAQS

Q1. Can the same array position be used more than once in a triplet?

No. Every valid triplet must use three different indices. Equal values remain allowed when they come from different positions.

Q2. Why must duplicate triplets be removed?

Different index combinations may contain the same three values. The answer requires unique value combinations rather than unique index combinations.

Q3. Why does the Brute Force Approach sort every valid triplet?

Sorting gives every triplet a consistent value order. Triplets formed through different index arrangements therefore become identical before set insertion.

Q4. Why is a fresh seenValues set created for every fixed index?

The set must contain only values belonging to the current fixed-index search. Reusing values from an earlier traversal could combine incompatible positions.

Q5. Why is nums[second] inserted after searching for thirdValue?

The lookup must use an earlier position. Inserting afterward prevents the current second index from acting as both the second and third element.

Q6. Why does the Optimal Approach skip duplicate values after finding a triplet?

Sorted duplicates appear next to one another. Moving past equal left and right values prevents the same value triplet from being added repeatedly.

ArraysTwo Pointer

Read Similar Blogs

Arrays

Row wise traversal

Given a matrix with N rows and M columns, print all elements row by row from left to right. Input: mat = [[1, 2, 3], [4, 5, 6]] Output: 1 2 3 4 5 6 Explanation: First row prints as 1 2 3 , then sec...

72.4k
Arrays

Main Diagonal Print

Given a matrix with N rows and M columns, print all elements present on the main diagonal. Input: mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] Output: 1 5 9 Explanation: Main diagonal cells are mat[0][0...

79.8k
Arrays

Search Element in Matrix

Input: mat = [[1, 2, 3], [7, 6, 8], [9, 2, 5]], X = 6 Output: {1, 1} Explanation: Target value 6 is present at row 1 and column 1 . Input: mat = [[3, 4, 5, 0], [2, 9, 8, 7]], X = 10 Output: {-1, -1...

110.4k
Comments0