The 3Sum problem is a popular coding challenge on LeetCode that tests your ability to implement efficient algorithms for finding combinations. This blog will walk you through various approaches, from the brute force method to optimized solutions, with complete explanations, time complexities, and Java implementations.
Problem Statement
3Sum: 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, and- Triplets should not contain duplicate sets.
You can return the answer in any order.
Approach 1: Brute Force (Naive Solution)
The most straightforward way to solve this problem is to use three nested loops to check all possible combinations of triplets. While this solution is simple to implement, it is highly inefficient.
Algorithm
- Use three loops to iterate over all triplets.
- Check if the sum of the triplet equals
0. - Store the triplet in the result set to avoid duplicates.
Java Code
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class ThreeSumBruteForce {
public static List<List<Integer>> threeSum(int[] nums) {
Set<List<Integer>> result = new HashSet<>();
int n = nums.length;
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) {
List<Integer> triplet = List.of(nums[i], nums[j], nums[k]);
triplet.sort(Integer::compareTo); // Sort to avoid duplicate sets
result.add(triplet);
}
}
}
}
return new ArrayList<>(result);
}
}Time Complexity
- Time: O(n3)O(n^3)O(n3), as we use three nested loops.
- Space: O(k)O(k)O(k), where kkk is the number of unique triplets.
Approach 2: Sorting + Two Pointers
This approach is much more efficient and uses sorting combined with the two-pointer technique to reduce the complexity.
Algorithm
- Sort the array to enable efficient duplicate handling and use of two pointers.
- Fix the first element of the triplet (
nums[i]). - Use two pointers (
leftandright) to find the remaining two elements. - Adjust pointers based on the sum.
Java Code
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class ThreeSumTwoPointers {
public static List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums); // Sort the array
for (int i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue; // Skip duplicates for the first number
int left = i + 1, right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
result.add(Arrays.asList(nums[i], nums[left], nums[right]));
while (left < right && nums[left] == nums[left + 1]) left++; // Skip duplicates for left
while (left < right && nums[right] == nums[right - 1]) right--; // Skip duplicates for right
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}
}Time Complexity
- Time: O(n2)O(n^2)O(n2), as we use sorting (O(nlogn)O(n \log n)O(nlogn)) and a two-pointer loop.
- Space: O(k)O(k)O(k), where kkk is the number of unique triplets stored in the result.
Approach 3: Hashing-Based Solution
Instead of using two pointers, we can leverage a hash set to store complements during the inner loop.
Algorithm
- Fix the first element of the triplet (
nums[i]). - Use a hash set to track elements in the inner loop.
- Check if the complement of the current number exists in the hash set.
Java Code
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
public class ThreeSumHashing {
public static List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums); // Sort to handle duplicates easily
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue; // Skip duplicates for the first number
HashSet<Integer> seen = new HashSet<>();
for (int j = i + 1; j < nums.length; j++) {
int complement = -nums[i] - nums[j];
if (seen.contains(complement)) {
result.add(Arrays.asList(nums[i], nums[j], complement));
while (j + 1 < nums.length && nums[j] == nums[j + 1]) j++; // Skip duplicates
}
seen.add(nums[j]);
}
}
return result;
}
}Time Complexity
- Time: O(n2)O(n^2)O(n2), as we iterate through the array and perform hash set operations.
- Space: O(n)O(n)O(n), for the hash set.
Conclusion
The two-pointer approach is the most efficient and widely used solution for the 3Sum problem. It strikes a balance between simplicity and performance, making it ideal for competitive programming and interviews. The hashing solution is a good alternative but requires extra space.
Try implementing these solutions and see which one works best for your needs!