Three Sum Problem Explained – Brute Force vs Two Pointer (Java)
Learn how to solve the Three Sum problem using Brute Force and Two Pointer approaches. Includes intuition, dry run, Java code, time complexity, interview tips, and production insights.
Introduction
Three Sum is one of the most frequently asked coding interview questions at companies like:
- Amazon
- Microsoft
- Meta
- Apple
- Netflix
- Uber
- Goldman Sachs
Although it extends the classic Two Sum concept, interviewers use it to evaluate whether a candidate can:
- Reduce a three-variable problem to a two-variable scan
- Eliminate duplicate triplets correctly
- Optimize from O(n³) to O(n²)
- Write clean and production-quality code
Understanding this problem is essential because it directly applies the Two Pointer pattern to a sorted array after reducing the problem dimension.
Problem Statement
Given an integer array nums, return all triplets [nums[i], nums[j], nums[k]] such that:
i != j,i != k,j != knums[i] + nums[j] + nums[k] == 0
The solution set must not contain duplicate triplets.
Example
Input
nums = [-1, 0, 1, 2, -1, -4]
Output
[[-1, -1, 2], [-1, 0, 1]]
Explanation
-1 + -1 + 2 = 0
-1 + 0 + 1 = 0
Approach 1 — Brute Force
Idea
Use three nested loops to try every combination of three elements.
i
↓
j
↓
k
↓
Check if nums[i] + nums[j] + nums[k] == 0
Java Code
import java.util.*;
public class ThreeSumBruteForce {
public 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 = Arrays.asList(nums[i], nums[j], nums[k]);
Collections.sort(triplet);
result.add(triplet);
}
}
}
}
return new ArrayList<>(result);
}
}
Complexity
| Complexity | Value |
|---|---|
| Time | O(n³) |
| Space | O(n) |
Why Brute Force is Bad?
For
1,000 Elements
the number of combinations becomes enormous.
n³
↓
1000 × 1000 × 1000
↓
1 Billion Combinations
Not suitable for production.
Approach 2 — Two Pointer (Optimal)
Core Idea
Sort the array first.
Fix the first element using an outer loop.
For the remaining two elements, use two pointers — one starting just after the fixed element, and one at the end.
Shrink the window based on the current sum.
Sort Array
↓
Fix nums[i]
↓
Left = i + 1
Right = n - 1
↓
Move Pointers
Algorithm
For each fixed element at index i:
Target = 0 - nums[i]
↓
left = i + 1
right = n - 1
↓
sum = nums[left] + nums[right]
↓
sum < Target → move left right
sum > Target → move right left
sum == Target → record triplet, skip duplicates
Dry Run
Array
[-1, 0, 1, 2, -1, -4]
After Sorting
[-4, -1, -1, 0, 1, 2]
Step 1 — Fix i = 0 (nums[i] = -4)
Left = 1 → -1
Right = 5 → 2
Sum = -1 + 2 = 1
Target = 4
1 < 4 → move Left right
Left = 2 → -1
Right = 5 → 2
Sum = -1 + 2 = 1
Still < 4 → move Left right
Left = 3 → 0
Right = 5 → 2
Sum = 0 + 2 = 2
Still < 4 → move Left right
Left = 4 → 1
Right = 5 → 2
Sum = 1 + 2 = 3
Still < 4 → Left crosses Right → Done
No triplet found for -4.
Step 2 — Fix i = 1 (nums[i] = -1)
Left = 2 → -1
Right = 5 → 2
Sum = -1 + 2 = 1
Target = 1
1 == 1 → Triplet Found: [-1, -1, 2]
Skip duplicates.
Left = 3 → 0
Right = 4 → 1
Sum = 0 + 1 = 1
1 == 1 → Triplet Found: [-1, 0, 1]
Skip duplicates.
Left crosses Right → Done
Step 3 — Fix i = 2 (nums[i] = -1, duplicate — skip)
Step 4 — Fix i = 3 (nums[i] = 0)
Left = 4 → 1
Right = 5 → 2
Sum = 1 + 2 = 3
Target = 0
3 > 0 → move Right left
Left crosses Right → Done
No new triplet.
Result
[[-1, -1, 2], [-1, 0, 1]]
Java Code
import java.util.*;
public class ThreeSum {
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++) {
// Skip duplicate values for the fixed element
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]));
// Skip duplicates for left pointer
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
// Skip duplicates for right pointer
while (left < right && nums[right] == nums[right - 1]) {
right--;
}
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}
}
Complexity
| Complexity | Value |
|---|---|
| Time | O(n²) |
| Space | O(1) (excluding output) |
Why Two Pointer Works?
Sorting the array enables a directional search.
Array (Sorted)
↓
Fix First Element
↓
Two Pointer Scan
↓
Sum Too Small → Move Left Right
↓
Sum Too Large → Move Right Left
↓
Sum == 0 → Record Triplet
Because the array is sorted, each pointer only moves in one direction.
This eliminates the need for an inner nested loop.
Average lookup per fixed element
O(n)
Example Walkthrough
Input
nums = [0, 0, 0]
After Sorting
[0, 0, 0]
Fix i = 0
Left = 1
Right = 2
Sum = 0 + 0 + 0 = 0
Triplet Found: [0, 0, 0]
Output
[[0, 0, 0]]
Input
nums = [1, 2, -2, -1]
After Sorting
[-2, -1, 1, 2]
Fix i = 0 (nums[i] = -2)
Left = 1 → -1
Right = 3 → 2
Sum = -2 + (-1) + 2 = -1
-1 < 0 → move Left right
Left = 2 → 1
Right = 3 → 2
Sum = -2 + 1 + 2 = 1
1 > 0 → move Right left
Left crosses Right → Done
Fix i = 1 (nums[i] = -1)
Left = 2 → 1
Right = 3 → 2
Sum = -1 + 1 + 2 = 2
2 > 0 → move Right left
Left crosses Right → Done
Output
[]
Edge Cases
All Zeros
Input
[0, 0, 0, 0]
Output
[[0, 0, 0]]
Only one unique triplet is returned despite multiple zeros.
All Positive Numbers
[1, 2, 3, 4]
Output
[]
No triplet sums to zero when all elements are positive.
All Negative Numbers
[-1, -2, -3, -4]
Output
[]
No triplet sums to zero when all elements are negative.
Mixed with Duplicates
[-2, 0, 0, 2, 2]
Output
[[-2, 0, 2]]
Duplicates are correctly skipped.
Production Applications
The Three Sum sorting and two-pointer pattern is used in real systems.
Examples include:
- Financial reconciliation matching three-way debits and credits
- Finding balanced load combinations in cloud resource allocation
- Detecting triplets in signal processing and anomaly detection
- Three-way join optimizations in databases
- Finding three correlated metrics in observability platforms
- Fraud detection with triple-entity matching
Sorting with a two-pointer scan enables efficient triplet discovery across large datasets.
Common Interview Mistakes
❌ Forgetting to sort the array before applying two pointers.
❌ Not skipping duplicate values for the outer fixed element.
❌ Not skipping duplicate values for left and right pointers after a match.
❌ Using a Set to handle duplicates (works but adds unnecessary overhead after sorting).
❌ Off-by-one error when the left pointer skips duplicates before incrementing.
❌ Returning values rather than indices (problem asks for values, not indices — verify the statement).
Follow-Up Questions
What if the target is not zero?
Generalize the problem to find triplets where
nums[i] + nums[j] + nums[k] == target
The approach is identical — replace the hardcoded 0 with the target value.
What is the Four Sum problem?
Fix two outer elements and apply Two Pointer for the remaining two.
Time Complexity
O(n³)
The same de-duplication logic applies at every level.
Can you solve Three Sum without sorting?
Yes, using a HashSet for the inner lookup, but de-duplicating without sorting requires extra bookkeeping.
Time Complexity
O(n²)
Space Complexity
O(n)
Sorting is preferred for clarity and lower constant factors.
How does Two Pointer guarantee no missed triplets?
Because the array is sorted, moving the left pointer right increases the sum, and moving the right pointer left decreases it. Every combination is explored in order, so no valid triplet is skipped.
Interview Tips
Interviewers often ask:
- Why sort first?
- How do you skip duplicates without a Set?
- Why is the time complexity O(n²) and not O(n³)?
- What happens when all elements are the same?
- What is the space complexity?
- Can you extend this to Four Sum?
- How do the two pointers converge?
- When do you move the left pointer versus the right pointer?
- What does the outer loop iterate over?
- Why do you start the outer loop at
i > 0when skipping duplicates?
Be prepared to explain the sorting step and duplicate-skipping logic before writing code.
Summary
Three Sum extends Two Sum by fixing one element and reducing the remaining two elements to a sorted Two Pointer scan. Sorting the array is critical — it enables directional movement of the pointers and makes duplicate skipping straightforward. The brute-force O(n³) approach is too slow for production. The Two Pointer approach achieves O(n²) time with O(1) extra space (excluding output), making it efficient and interview-ready.
Key Takeaways
- Sort the array before applying Two Pointer.
- Fix the first element with an outer loop.
- Apply Two Pointer to the remaining sub-array.
- Skip duplicate values at every level — outer loop, left pointer, and right pointer.
- Move the left pointer right when the sum is too small.
- Move the right pointer left when the sum is too large.
- Record the triplet and narrow both pointers when the sum equals the target.
- Achieve O(n²) time complexity with constant extra space.