In 3 Sum problem, we have given an array nums of n integers, find all the unique triplets that sum up to 0.
Table of Contents
Example
Input:
nums = {-1, 0, 1, 2, -1, -4}
Output:
{-1, 0, 1}, {-1, 2, -1}
Naive Approach for 3 Sum problem
The Brute force approach to solve the problem is to test all the possible triplets and pick those that sums up to zero.
This could be achieved using three nested loops.
- Create a HashSet to store the triplets with sum 0.
- Run a loop for i = 0 to (n – 1), where n is the number of elements in the array.
- Run a nested loop for j = (i + 1) to (n – 1).
- Nest one more loop for k = (j + 1) to (n – 1).
- These three loop forms a unique triplet, nums[i], nums[j] and nums[k]. The sum of the triplet is (nums[i] + nums[j] + nums[k]). If the sum is zero, add this triplet(i, j, k) to the triplets HashSet.
- All the triplets summing to zero are present in HashSet, so print the content of HashSet.
JAVA Code for 3 Sum
public class ThreeSum {
private static void printUniqueTriplets(int[] nums) {
int n = nums.length;
// Created a set of triplets to avoid duplicates
HashSet<Triplet> triplets = new HashSet<>();
// Use 3 nested loop to check all the possible combinations
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
// If this triplet sums to zero, add it in the set
int sum = nums[i] + nums[j] + nums[k];
if (sum == 0) {
triplets.add(new Triplet(nums[i], nums[j], nums[k]));
}
}
}
}
// Print the unique triplets
for (Triplet triplet : triplets) {
System.out.println(triplet.ele[0] + " " + triplet.ele[1] + " "
+ triplet.ele[2]);
}
}
public static void main(String[] args) {
// Example
int nums[] = new int[]{-1, 0, 1, 2, -1, -4};
printUniqueTriplets(nums);
}
// class representing a triplet
static class Triplet {
int ele[];
public Triplet(int first, int second, int third) {
ele = new int[3];
ele[0] = first;
ele[1] = second;
ele[2] = third;
// Store the triplets in ascending order, so that this could be used
// in checking duplicates
Arrays.sort(ele);
}
// Two triplets are equal if elements in them are same
@Override
public boolean equals(Object o) {
Triplet t = (Triplet) o;
return (Arrays.compare(ele, t.ele) == 0);
}
@Override
public int hashCode() {
return Arrays.hashCode(ele);
}
}
}-1 -1 2 -1 0 1
C++ Code for 3 Sum
#include <bits/stdc++.h>
using namespace std;
// structure representing a triplet
struct Triplet {
int ele[3];
bool operator==(const Triplet& t) const {
return (this->ele[0] == t.ele[0] && this->ele[1] == t.ele[1] && this->ele[2] == t.ele[2]);
}
};
// custom hash function for triplet
class MyHash {
public:
size_t operator()(const Triplet& t) const {
return t.ele[0] + 10 * t.ele[1] + 100 * t.ele[2];
}
};
void printUniqueTriplets(int *nums, int n) {
// Created a set of triplets to avoid duplicates
unordered_set<Triplet, MyHash> triplets;
// Use 3 nested loop to check all the possible combinations
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
int sum = nums[i] + nums[j] + nums[k];
// If this triplet sums to zero, add it in the set
if (sum == 0) {
Triplet triplet;
int e[3];
e[0] = nums[i];
e[1] = nums[j];
e[2] = nums[k];
sort(e, e + 3);
triplet.ele[0] = e[0];
triplet.ele[1] = e[1];
triplet.ele[2] = e[2];
triplets.insert(triplet);
}
}
}
}
// Print the unique triplets
for (auto itr = triplets.begin(); itr != triplets.end(); itr++) {
cout<<itr->ele[0]<<" "<<itr->ele[1]<<" "<<itr->ele[2]<<endl;
}
}
int main() {
// Example
int nums[] = {-1, 0, 1, 2, -1, -4};
printUniqueTriplets(nums, sizeof(nums) / sizeof(nums[0]));
}-1 -1 2 -1 0 1
Complexity Analysis
Time Complexity = O(n3)
Space Complexity = O(1)
where n is the number of elements in the array.
Optimal Approach for 3 Sum problem
The better approach is to use 3 pointer method.
- Sort the array in ascending order.
- For an element at index i, try to make a sum of -nums[i] (negative of nums[i]) with two elements from the elements ahead of it, so that the triplet sums to zero.
- Two pointer approach is applicable here to find the required sum(-nums[i]) because the array is sorted.
- If there exists two elements that sum up to required sum, add the triplet (two elements and nums[i]) to the answer set.
- Print the answer set.
JAVA Code for 3 Sum
import java.util.Arrays;
import java.util.HashSet;
public class ThreeSum {
private static void printUniqueTriplets(int[] nums) {
int n = nums.length;
Arrays.sort(nums);
HashSet<Triplet> triplets = new HashSet<>();
for (int i = 0; i < n; i++) {
int req = -nums[i];
int left = i + 1;
int right = n - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == req) {
triplets.add(new Triplet(nums[i], nums[left], nums[right]));
// Check for more triplets
left++;
right--;
} else if (sum < req) {
left++;
} else {
right--;
}
}
}
// Print the unique triplets
for (Triplet triplet : triplets) {
System.out.println(triplet.ele[0] + " " + triplet.ele[1] + " "
+ triplet.ele[2]);
}
}
public static void main(String[] args) {
int nums[] = new int[]{-1, 0, 1, 2, -1, -4};
printUniqueTriplets(nums);
}
// class representing a triplet
static class Triplet {
int ele[];
public Triplet(int first, int second, int third) {
ele = new int[3];
ele[0] = first;
ele[1] = second;
ele[2] = third;
// Store the triplets in ascending order, so that this could be used
// in checking duplicates
Arrays.sort(ele);
}
// Two triplets are equal if elements in them are same
@Override
public boolean equals(Object o) {
Triplet t = (Triplet) o;
return (Arrays.compare(ele, t.ele) == 0);
}
@Override
public int hashCode() {
return Arrays.hashCode(ele);
}
}
}-1 -1 2 -1 0 1
C++ Code for 3 Sum
#include <bits/stdc++.h>
using namespace std;
// structure representing a triplet
struct Triplet {
int ele[3];
bool operator==(const Triplet& t) const {
return (this->ele[0] == t.ele[0] && this->ele[1] == t.ele[1] && this->ele[2] == t.ele[2]);
}
};
// custom hash function for triplet
class MyHash {
public:
size_t operator()(const Triplet& t) const {
return t.ele[0] + 10 * t.ele[1] + 100 * t.ele[2];
}
};
void printUniqueTriplets(int *nums, int n) {
sort(nums, nums + n);
// Created a set of triplets to avoid duplicates
unordered_set<Triplet, MyHash> triplets;
for (int i = 0; i < n; i++) {
int req = -nums[i];
int left = i + 1;
int right = n - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == req) {
// Add this triplet to the set
Triplet triplet;
int e[3];
e[0] = nums[i];
e[1] = nums[left];
e[2] = nums[right];
sort(e, e + 3);
triplet.ele[0] = e[0];
triplet.ele[1] = e[1];
triplet.ele[2] = e[2];
triplets.insert(triplet);
// Check for more triplets
left++;
right--;
} else if (sum < req) {
left++;
} else {
right--;
}
}
}
// Print the unique triplets
for (auto itr = triplets.begin(); itr != triplets.end(); itr++) {
cout<<itr->ele[0]<<" "<<itr->ele[1]<<" "<<itr->ele[2]<<endl;
}
}
int main() {
// Example
int nums[] = {-1, 0, 1, 2, -1, -4};
printUniqueTriplets(nums, sizeof(nums) / sizeof(nums[0]));
}-1 -1 2 -1 0 1
Complexity Analysis
Time Complexity = O(n2)
Space Complexity = O(1)
where n is the number of elements in the array.