Approach Summary
Sort the array, fix one element, then use two pointers for the rest. Skip duplicates carefully to avoid duplicate triplets.
Practice Mode
2 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Brute Force (3 Nested Loops with Set) | O(n³) | O(n) for set deduplication | Generate all triplets with 3 loops and deduplicate using a set of sorted tuples. |
| 2 Approach 2: Sort and Two Pointers (Optimal) | O(n²) | O(1) auxiliary | Sort the array, fix each candidate nums[i], and use two pointers to find pairs in linear time. |
Step 1: Baseline
Approach 1: Brute Force (3 Nested Loops with Set)
Time: O(n³)
Space: O(n) for set deduplication
Loop i from 0 to n - 1, j from i + 1 to n - 1, and k from j + 1 to n - 1. When nums[i] + nums[j] + nums[k] == 0, sort the triplet and insert into a set to avoid duplicates. Because n can be up to 3,000, n³ is ~2.7 × 10¹⁰ operations, which will heavily timeout.
Approach 1: Brute Force (3 Nested Loops with Set) Implementation
Approach 1: Brute Force (3 Nested Loops with Set)
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Set<List<Integer>> set = new HashSet<>();
int n = nums.length;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; 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);
set.add(triplet);
}
}
}
}
return new ArrayList<>(set);
}
}class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
set<vector<int>> setTriplets;
int n = nums.size();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
if (nums[i] + nums[j] + nums[k] == 0) {
vector<int> triplet = {nums[i], nums[j], nums[k]};
sort(triplet.begin(), triplet.end());
setTriplets.insert(triplet);
}
}
}
}
return vector<vector<int>>(setTriplets.begin(), setTriplets.end());
}
};def three_sum(nums: list[int]) -> list[list[int]]:
n = len(nums)
triplets = set()
for i in range(n):
for j in range(i + 1, n):
for k in range(j + 1, n):
if nums[i] + nums[j] + nums[k] == 0:
triplets.add(tuple(sorted([nums[i], nums[j], nums[k]])))
return [list(t) for t in triplets]function threeSum(nums) {
const n = nums.length;
const set = new Set();
const result = [];
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
for (let k = j + 1; k < n; k++) {
if (nums[i] + nums[j] + nums[k] === 0) {
const sorted = [nums[i], nums[j], nums[k]].sort((a, b) => a - b);
const key = sorted.join(',');
if (!set.has(key)) {
set.add(key);
result.push(sorted);
}
}
}
}
}
return result;
} Step 2: Most Optimized
Approach 2: Sort and Two Pointers (Optimal)
Time: O(n²)
Space: O(1) auxiliary
After sorting, fix nums[i]. If i > 0 and nums[i] == nums[i - 1], skip it to prevent duplicate triplets. Initialize j = i + 1 and k = n - 1. If nums[i] + nums[j] + nums[k] == 0, append the triplet, and increment j while skipping identical adjacent values, and decrement k while skipping identical values. If the sum is negative, we need a larger value so increment j; if positive, decrement k. This reduces time complexity from cubic to quadratic.
Approach 2: Sort and Two Pointers (Optimal) Implementation
Approach 2: Sort and Two Pointers (Optimal)
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
int n = nums.length;
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < n; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int j = i + 1;
int k = n - 1;
while (j < k) {
int sum = nums[i] + nums[j] + nums[k];
if (sum == 0) {
result.add(Arrays.asList(nums[i], nums[j], nums[k]));
j++;
k--;
while (j < k && nums[j] == nums[j - 1]) {
j++;
}
while (j < k && nums[k] == nums[k + 1]) {
k--;
}
} else if (sum < 0) {
j++;
} else {
k--;
}
}
}
return result;
}
}class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int n = nums.size();
vector<vector<int>> result;
sort(nums.begin(), nums.end());
for (int i = 0; i < n; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int j = i + 1;
int k = n - 1;
while (j < k) {
int sum = nums[i] + nums[j] + nums[k];
if (sum == 0) {
result.push_back({nums[i], nums[j], nums[k]});
j++;
k--;
while (j < k && nums[j] == nums[j - 1]) {
j++;
}
while (j < k && nums[k] == nums[k + 1]) {
k--;
}
} else if (sum < 0) {
j++;
} else {
k--;
}
}
}
return result;
}
};def three_sum(nums: list[int]) -> list[list[int]]:
nums.sort()
n = len(nums)
result = []
for i in range(n):
if i > 0 and nums[i] == nums[i - 1]:
continue
j = i + 1
k = n - 1
while j < k:
total = nums[i] + nums[j] + nums[k]
if total == 0:
result.append([nums[i], nums[j], nums[k]])
j += 1
k -= 1
while j < k and nums[j] == nums[j - 1]:
j += 1
while j < k and nums[k] == nums[k + 1]:
k -= 1
elif total < 0:
j += 1
else:
k -= 1
return resultfunction threeSum(nums) {
nums.sort((a, b) => a - b);
const n = nums.length;
const result = [];
for (let i = 0; i < n; i++) {
if (i > 0 && nums[i] === nums[i - 1]) continue;
let j = i + 1;
let k = n - 1;
while (j < k) {
const sum = nums[i] + nums[j] + nums[k];
if (sum === 0) {
result.push([nums[i], nums[j], nums[k]]);
j++;
k--;
while (j < k && nums[j] === nums[j - 1]) j++;
while (j < k && nums[k] === nums[k + 1]) k--;
} else if (sum < 0) {
j++;
} else {
k--;
}
}
}
return result;
}Edge Cases to Watch
- Array with fewer than 3 elements (returns [])
- All zeros [0, 0, 0, 0] (returns single triplet [0, 0, 0])
- Multiple identical duplicate numbers where duplicate triplets must be prevented
- No triplet sums to zero
Algorithmic Pattern
View Pattern Guide →
Master the Two Pointers Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Two Pointers pattern.
Framework: Two Pointers • Interview Prep: Tested at FAANG •
Explore all Two Pointers problems & invariants →
How to Recognize This Pattern
- Find all triplets summing to zero
- No duplicate triplets
Complexity Analysis
Time Complexity
O(n²)
Space Complexity
O(n)
Tags
Array Two Pointers Sorting
Frequently Asked Questions
What is the optimal time and space complexity for 3Sum?
The optimal solution for 3Sum achieves O(n²) runtime complexity and requires O(n) auxiliary space. Sorting takes O(n log n). The outer loop runs n times, and the two-pointer inner scan takes O(n) per element, totaling O(n²) time. Auxiliary space is O(1) or O(log n) depending on the sorting algorithm implementation, excluding space for the returned result list.
How do I identify that 3Sum requires the Two Pointers pattern?
In technical interviews, look for key problem signals: Find all triplets summing to zero; No duplicate triplets. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Two Pointers strategy.
What critical edge cases must be handled in 3Sum?
Essential edge cases to verify include: Array with fewer than 3 elements (returns []); All zeros [0, 0, 0, 0] (returns single triplet [0, 0, 0]); Multiple identical duplicate numbers where duplicate triplets must be prevented; No triplet sums to zero. Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask 3Sum?
3Sum is a Medium-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Facebook, Amazon, Google, Adobe.