The 3Sum problem is one of the most popular problems on LeetCode.
It looks simple, but many developers struggle with it because of duplicate handling and choosing the right approach.
This article explains both correct approaches:
- HashMap / HashSet based solution
- Sorting + Two Pointer solution (optimal)
So you understand why one is better, not just how to code it.
Problem Statement
You are given an integer array nums.
Find all unique triplets [nums[i], nums[j], nums[k]] such that:
nums[i] + nums[j] + nums[k] == 0
Rules
- Triplets must be unique
- Order inside a triplet does not matter
- Order of output does not matter
Example
Input
nums = [-1, 0, 1, 2, -1, -4]
Output
[[-1, -1, 2], [-1, 0, 1]]
Brute Force (Why We Avoid It)
Using three nested loops gives:
Time Complexity: O(n³)
This approach:
- Is too slow
- Fails large inputs
- Is not acceptable in interviews
We need better strategies.
Approach 1: HashMap / HashSet Based Solution
This is often the first optimized approach people think of.
Idea
For every nums[i], we try to solve a 2Sum problem using a HashSet.
Steps:
- Fix one number
nums[i] - Use a HashSet to track visited numbers
- For each
nums[j], check if-(nums[i] + nums[j])exists - Use a Set to avoid duplicate triplets
Java HashSet Solution
public List<List<Integer>> threeSum(int[] nums) {
Set<List<Integer>> result = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
Set<Integer> seen = new HashSet<>();
for (int j = i + 1; j < nums.length; j++) {
int third = -nums[i] - nums[j];
if (seen.contains(third)) {
List<Integer> triplet = Arrays.asList(nums[i], nums[j], third);
Collections.sort(triplet);
result.add(triplet);
}
seen.add(nums[j]);
}
}
return new ArrayList<>(result);
}
Python HashSet Solution
def threeSum(nums):
result = set()
for i in range(len(nums)):
seen = set()
for j in range(i + 1, len(nums)):
third = -nums[i] - nums[j]
if third in seen:
triplet = tuple(sorted([nums[i], nums[j], third]))
result.add(triplet)
seen.add(nums[j])
return list(result)
Complexity Analysis (HashMap Approach)
| Metric | Value |
|---|---|
| Time | O(n²) |
| Space | O(n) |
Drawbacks of HashMap Approach
This approach works, but it has problems:
- Extra space is required
- Sorting each triplet adds overhead
- Duplicate handling is indirect
- Output order is unpredictable
- Harder to reason about correctness
Because of this, interviewers usually prefer the two-pointer solution.
Approach 2: Sorting + Two Pointers (Best Approach)
This is the most accepted and cleanest solution.
Why Sorting Helps
Sorting allows us to:
- Use two pointers efficiently
- Skip duplicates easily
- Control sum movement logically
Step-by-Step Logic
- Sort the array
- Fix
nums[i] - Use two pointers:
left = i + 1right = n - 1
- Adjust pointers based on sum
- Skip duplicates carefully
Java Two-Pointer Solution
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
int left = i + 1;
int 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++;
while (left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}
C++ Two-Pointer Solution
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size() - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
int left = i + 1, right = nums.size() - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
result.push_back({nums[i], nums[left], nums[right]});
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}
Python Two-Pointer Solution
def threeSum(nums):
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue
left, right = i + 1, len(nums) - 1
while left < right:
s = nums[i] + nums[left] + nums[right]
if s == 0:
result.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
elif s < 0:
left += 1
else:
right -= 1
return result
Comparing Both Approaches
| Feature | HashMap | Two Pointers |
|---|---|---|
| Time | O(n²) | O(n²) |
| Space | O(n) | O(1) |
| Duplicate Control | Indirect | Direct |
| Code Clarity | Medium | High |
| Interview Preference | Low | High |
Common Mistakes
- Forgetting to skip duplicates
- Using HashMap and missing unique constraint
- Returning repeated triplets
- Not sorting when using two pointers
Final Thoughts
The HashMap approach helps understand the problem, but the
sorting + two-pointer approach is the one you should master.
If you can:
- Explain both
- Implement both
- Compare both
Then you truly understand 3Sum, not just the solution.
