3Sum is one of the most important interview problems because it introduces a powerful pattern:
Fix one element and reduce the problem to a smaller known problem.
The key insight is that after fixing one number, the remaining task becomes a 2-Sum problem, which can be solved efficiently using the Two Pointer technique.
Problem Statement
Given an integer array nums, return all unique triplets:
nums[i] + nums[j] + nums[k] = 0
such that:
i != j
i != k
j != k
and no duplicate triplets are allowed.
Brute Force Intuition
Generate every possible triplet using three nested loops.
for(i)
for(j)
for(k)
For each triplet:
- Calculate the sum.
- If sum equals 0, add it to the answer.
- Use a Set to avoid duplicates.
Interview Explanation
The brute force approach generates every possible triplet and checks whether its sum equals zero. Since there are three nested loops, we examine O(n³) combinations, making it inefficient for large inputs.
Complexity
Time : O(n³)
Space : O(number of triplets)
Moving Towards the Optimal Solution
Given:
a + b + c = 0
Fix one element:
a = nums[i]
Now we need:
b + c = -a
This becomes a 2-Sum problem.
After sorting the array, we can solve this 2-Sum using Two Pointers.
Key Observation
After sorting:
[-4,-1,-1,0,1,2]
Fix:
-1
Need:
b + c = 1
Use:
left = i + 1;
right = n - 1;
Now:
sum < target -> move left
sum > target -> move right
sum == target -> triplet found
Optimal Approach
Step 1
Sort the array.
Arrays.sort(nums);
Step 2
Fix one element.
for(int i = 0; i < n - 2; i++)
Step 3
Use two pointers.
left = i + 1;
right = n - 1;
Step 4
Check the sum.
nums[i] + nums[left] + nums[right]
Step 5
Skip duplicates from:
- Fixed element
i - Left pointer
- Right pointer
This ensures unique triplets only.
Dry Run
Input
[-4,-1,-1,0,1,2]
i = 1
nums[i] = -1
left = 2
right = 5
Sum
-1 + (-1) + 2 = 0
Triplet:
[-1,-1,2]
Move pointers.
Again
-1 + 0 + 1 = 0
Triplet:
[-1,0,1]
Answer:
[
[-1,-1,2],
[-1,0,1]
]
Optimal Java Solution
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<>();
int n = nums.length;
for (int i = 0; i < n - 2; i++) {
// Skip duplicate fixed elements
if (i > 0 && nums[i] == nums[i - 1])
continue;
int left = i + 1;
int right = n - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
ans.add(Arrays.asList(
nums[i],
nums[left],
nums[right]
));
left++;
right--;
// Skip duplicate left values
while (left < right &&
nums[left] == nums[left - 1]) {
left++;
}
// Skip duplicate right values
while (left < right &&
nums[right] == nums[right + 1]) {
right--;
}
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return ans;
}
}
Why Duplicate Skipping Works
Consider:
[-2,0,0,0,2,2]
Without skipping duplicates:
[-2,0,2]
[-2,0,2]
[-2,0,2]
would be generated multiple times.
Skipping duplicates ensures each unique triplet appears exactly once.
Complexity Analysis
Time : O(n²)
Space : O(1)
Ignoring the output list.
Sorting takes:
O(n log n)
and the Two Pointer scan runs:
O(n²)
which dominates the complexity.
Pattern Recognition
Whenever you see:
- 3Sum
- Triplets
- Unique combinations
- Sum equals target
Think:
Sort
→ Fix one element
→ Solve remaining using Two Pointers
Similarly:
2 Sum -> HashMap / Two Pointers
3 Sum -> Fix 1 + Two Pointers
4 Sum -> Fix 2 + Two Pointers
K Sum -> Recursive reduction
Interview One-Liner
I sort the array, fix one element, and use the Two Pointer technique to find the remaining two elements whose sum balances the fixed value. Duplicate skipping at all three positions ensures unique triplets while achieving O(n²) time complexity.
Top comments (0)