The 3Sum problem in LeetCode is a classic programming challenge that revolves around finding unique triplets in an array whose sum adds up to zero. In this blog post, we’ll dive deep into understanding the problem statement, exploring different approaches, and finally implementing an optimal solution to crack the 3Sum problem.
Problem Statement
Imagine facing an array of integers, each holding a numeric value. Your task is to identify distinct triplets within this array, namely sets of three numbers [nums[i], nums[j], nums[k]] satisfying the following conditions: i != j, i != k, j != k, and nums[i] + nums[j] + nums[k] equals 0.
The catch? The solution set must exclude any duplicate triplets, preserving only the unique combinations.
Examples
Example 1:
Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]]
Explanation:
- Adding nums[0] + nums[1] + nums[2] results in (-1) + 0 + 1 = 0.
- Equally, nums[1] + nums[2] + nums[4] evaluates to 0 + 1 + (-1) = 0.
- Additionally, nums[0] + nums[3] + nums[4] sums up to (-1) + 2 + (-1) = 0. The distinct triplets found are [-1,0,1] and [-1,-1,2].
Please note, the order of appearance and arrangement of the triplets are both insignificant.
Example 2:
Input: nums = [0,1,1]
Output: []
Explanation: In this case, no possible triplet combination can equate to 0.
Example 3:
Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The single plausible triplet indeed sums up to 0.
Constraints:
3 <= nums.length <= 3000: The array will consist of at least 3 but no more than 3000 elements.-105 <= nums[i] <= 105: The integer values within the array will range between -105 and 105.
Now that you grasp the essence of the 3Sum problem, let’s delve into different strategies to tackle it efficiently. By understanding the scenarios, constraints, and potential solutions, you’ll be better equipped to unravel the mysteries of this intriguing challenge.
Brute Force/Naive Approach
Let’s start by discussing the brute force approach to solving the 3Sum problem. While this approach isn’t the most efficient, it provides a solid foundation to build upon.
Algorithm
The brute force approach involves checking all possible triplets using three nested loops. Among these triplets, we consider the ones whose sum equals the target, which in this case is zero. Before considering these triplets, we ensure they are sorted in ascending order to maintain uniqueness.
Here’s a step-by-step breakdown of the algorithm:
- Declare a set data structure to store unique triplets.
- Use the first loop (i) to iterate through the array from 0 to n-1.
- Inside the first loop, use the second loop (j) to iterate from i+1 to n-1.
- Inside the second loop, use the third loop (k) to iterate from j+1 to n-1.
- Calculate the sum of the triplet (arr[i] + arr[j] + arr[k]).
- If the sum equals zero, sort the triplet and insert it into the set.
- Return the list of triplets stored in the set.
Here’s the code implementation of the brute force/naive approach in C++, Java, and Python:
- C++
- Java
- Python
vector<vector<int>> triplet(int n, vector<int> &arr) {
set<vector<int>> st;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
if (arr[i] + arr[j] + arr[k] == 0) {
vector<int> temp = {arr[i], arr[j], arr[k]};
sort(temp.begin(), temp.end());
st.insert(temp);
}
}
}
}
vector<vector<int>> ans(st.begin(), st.end());
return ans;
}import java.util.*;
class Solution {
public List<List<Integer>> triplet(int n, List<Integer> arr) {
Set<List<Integer>> st = new HashSet<>();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
if (arr.get(i) + arr.get(j) + arr.get(k) == 0) {
List<Integer> temp = new ArrayList<>(Arrays.asList(arr.get(i), arr.get(j), arr.get(k)));
Collections.sort(temp);
st.add(temp);
}
}
}
}
List<List<Integer>> ans = new ArrayList<>(st);
return ans;
}
}
class Solution:
def triplet(self, n, arr):
st = set()
for i in range(n):
for j in range(i + 1, n):
for k in range(j + 1, n):
if arr[i] + arr[j] + arr[k] == 0:
temp = [arr[i], arr[j], arr[k]]
temp.sort()
st.add(tuple(temp))
ans = [list(item) for item in st]
return ans
Complexity Analysis
- Time Complexity: O(N3 * log(no. of unique triplets)), where N is the size of the array.
- Space Complexity: O(2 * no. of unique triplets) as we use a set data structure and a list to store the triplets.
Want to crack the DSA Interview in just 75 days? Practice Blind 75 Now!
Using Hash Map/Hash Table
While the brute force approach works, it’s not the most efficient solution. Let’s explore a better approach that reduces the number of loops and optimizes the algorithm.
Algorithm
In this approach, we aim to eliminate the third loop by deriving a formula to calculate the third element (arr[k]) based on the other two elements. This formula is: arr[k] = -(arr[i] + arr[j]).
To achieve this, we’ll use two nested loops: one for the fixed element (i) and another for the moving element (j). We’ll also employ a HashSet to store elements between i and j. This way, we can search for the third element without needing a third loop.
Here’s how the algorithm works:
- Declare a set data structure to store unique triplets.
- Use the first loop (i) to iterate through the array from 0 to n-1.
- Inside the first loop, use the second loop (j) to iterate from i+1 to n-1.
- Before the second loop, declare a HashSet to store elements between i and j.
- Calculate the value of the third element using the formula -(arr[i] + arr[j]).
- If the third element exists in the HashSet, sort the triplet and insert it into the set.
- Insert the j-th element (arr[j]) into the HashSet.
- Return the list of triplets stored in the set.
Here’s the code implementation of the HashSet approach in C++, Java, and Python:
- C++
- Java
- Python
vector<vector<int>> triplet(int n, vector<int> &arr) {
set<vector<int>> st;
for (int i = 0; i < n; i++) {
set<int> hashset;
for (int j = i + 1; j < n; j++) {
int third = -(arr[i] + arr[j]);
if (hashset.find(third) != hashset.end()) {
vector<int> temp = {arr[i], arr[j], third};
sort(temp.begin(), temp.end());
st.insert(temp);
}
hashset.insert(arr[j]);
}
}
vector<vector<int>> ans(st.begin(), st.end());
return ans;
}
import java.util.*;
class Solution {
public List<List<Integer>> triplet(int n, List<Integer> arr) {
Set<List<Integer>> st = new HashSet<>();
for (int i = 0; i < n; i++) {
Set<Integer> hashset = new HashSet<>();
for (int j = i + 1; j < n; j++) {
int third = -(arr.get(i) + arr.get(j));
if (hashset.contains(third)) {
List<Integer> temp = Arrays.asList(arr.get(i), arr.get(j), third);
Collections.sort(temp);
st.add(temp);
}
hashset.add(arr.get(j));
}
}
return new ArrayList<>(st);
}
}
class Solution:
def triplet(self, n, arr):
st = set()
for i in range(n):
hashset = set()
for j in range(i + 1, n):
third = -(arr[i] + arr[j])
if third in hashset:
temp = [arr[i], arr[j], third]
temp.sort()
st.add(tuple(temp))
hashset.add(arr[j])
return list(st)
Complexity Analysis
- Time Complexity: O(N2 * log(no. of unique triplets)), where N is the size of the array.
- Space Complexity: O(2 * no. of unique triplets) + O(N) for the HashSet and list storage.
Three Pointer approach
Finally, let’s explore the optimal approach to solving the 3Sum problem. This approach significantly improves efficiency by reducing the number of loops and eliminating the need for a HashSet.
Algorithm
The optimal approach involves sorting the array and then using two moving pointers (j and k) to find the appropriate values of arr[j] and arr[k]. We’ll fix a pointer (i) and use the other two pointers to efficiently locate the elements that yield the target sum of zero.
Here’s the breakdown of the algorithm:
- Sort the entire array.
- Use a loop (i) to iterate through the array from 0 to n-1.
- Remove duplicate values by skipping elements that are the same as the previous one.
- Initialize two pointers (j and k) where j starts from i+1 and k starts from the last index.
- Move the pointers j and k while checking the sum of the three elements (arr[i] + arr[j] + arr[k]).
- If the sum is less than zero, increase j to get a bigger value.
- If the sum is greater than zero, decrease k to get a smaller value.
- If the sum equals 0, insert the triplet
[arr[i], arr[j], arr[k]]into the answer, and increment j and decrement k while skipping duplicates. - Return the list of unique triplets.
Here’s the code implementation of the optimal approach using a three-pointer in C++, Java, and Python:
- C++
- Java
- Python
vector<vector<int>> triplet(int n, vector<int> &arr) {
vector<vector<int>> ans;
sort(arr.begin(), arr.end());
for (int i = 0; i < n; i++) {
if (i != 0 && arr[i] == arr[i - 1]) continue;
int j = i + 1;
int k = n - 1;
while (j < k) {
int sum = arr[i] + arr[j] + arr[k];
if (sum < 0) {
j++;
} else if (sum > 0) {
k--;
} else {
vector<int> temp = {arr[i], arr[j], arr[k]};
ans.push_back(temp);
j++;
k--;
while (j < k && arr[j] == arr[j - 1]) j++;
while (j < k && arr[k] == arr[k + 1]) k--;
}
}
}
return ans;
}
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class ThreeSum {
public List<List<Integer>> triplet(int[] arr) {
List<List<Integer>> ans = new ArrayList<>();
Arrays.sort(arr);
for (int i = 0; i < arr.length; i++) {
if (i > 0 && arr[i] == arr[i - 1]) continue;
int j = i + 1;
int k = arr.length - 1;
while (j < k) {
int sum = arr[i] + arr[j] + arr[k];
if (sum < 0) {
j++;
} else if (sum > 0) {
k--;
} else {
List<Integer> temp = new ArrayList<>();
temp.add(arr[i]);
temp.add(arr[j]);
temp.add(arr[k]);
ans.add(temp);
j++;
k--;
while (j < k && arr[j] == arr[j - 1]) j++;
while (j < k && arr[k] == arr[k + 1]) k--;
}
}
}
return ans;
}
}
def triplet(arr):
ans = []
arr.sort()
for i in range(len(arr)):
if i > 0 and arr[i] == arr[i - 1]:
continue
j = i + 1
k = len(arr) - 1
while j < k:
sum = arr[i] + arr[j] + arr[k]
if sum < 0:
j += 1
elif sum > 0:
k -= 1
else:
temp = [arr[i], arr[j], arr[k]]
ans.append(temp)
j += 1
k -= 1
while j < k and arr[j] == arr[j - 1]:
j += 1
while j < k and arr[k] == arr[k + 1]:
k -= 1
return ansComplexity Analysis
- Time Complexity: O(NlogN) + O(N^2), where N is the size of the array.
- Space Complexity: O(no. of quadruplets) – Since we only use space to store the answer, this can be approximated as O(1).
Wrapping Up
In this blog post, we’ve explored different approaches to tackle the 3Sum problem, ranging from brute force to optimal solutions. We’ve seen how the efficiency of the algorithm improves as we refine our approach, eliminating unnecessary loops and optimizing search operations. By understanding the core concepts and implementing the provided code examples, you’re now equipped to confidently solve the 3Sum problem and similar challenges. Mastering algorithmic problem-solving requires practice and a deep understanding of the underlying principles. Happy coding!
Reference
- LeetCode Problem
