These are the notes for DSA episode 6. 3Sum (LeetCode 15) asks for every unique triplet that adds up to zero. Three loops take O(n³) and print the same triplet more than once. Sorting the array unlocks the two pointer technique: fix one number, then walk two pointers towards each other, for O(n²) time and no duplicates. Every program below was run in the SyntaxPilot compiler (8-second time limit), and the outputs shown are real.
The problem, in real life
A shop keeps a ledger: money in is positive, money out is negative. An auditor looks for money moving in a circle: groups of three entries that cancel out to exactly zero, like +5, -3, -2. The report must list each group once, even if the same three amounts appear in several places.
Problem statement
Given an integer array nums, return all triplets [nums[i], nums[j], nums[k]] with i, j, k different and nums[i] + nums[j] + nums[k] == 0. The answer must not contain duplicate triplets. Constraints: 3 ≤ n ≤ 3000, -10⁵ ≤ nums[i] ≤ 10⁵.
| nums | answer |
|---|---|
| [-1, 0, 1, 2, -1, -4] | [[-1, -1, 2], [-1, 0, 1]] |
| [0, 0, 0, 0] | [[0, 0, 0]] |
| [0, 1, 1] | [] |
| [-2, 0, 1, 1, 2] | [[-2, 0, 2], [-2, 1, 1]] |
Brute force, take 1: three loops
import java.util.*;
public class Main {
static List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
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)
res.add(Arrays.asList(nums[i], nums[j], nums[k]));
return res;
}
public static void main(String[] args) {
System.out.println(threeSum(new int[]{-1, 0, 1, 2, -1, -4}));
}
}
Output:
[[-1, 0, 1], [-1, 2, -1], [0, 1, -1]]
[-1, 0, 1] and [0, 1, -1] are the same group in a different order. Wrong output.
Brute force, take 2: sort each triplet, use a HashSet
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> t = Arrays.asList(nums[i], nums[j], nums[k]);
Collections.sort(t);
set.add(t);
}
return new ArrayList<>(set);
Output for the example:
[[-1, -1, 2], [-1, 0, 1]]
Correct. But on 5,000 entries:
int n = 5000, nums[] = new int[n];
for (int i = 0; i < n; i++) nums[i] = (int) (i * 7919L % 20001) - 10000;
System.out.println(threeSum(nums).size() + " triplets");
Result: Time Limit Exceeded.
Why it is slow
There are n(n-1)(n-2)/6 triples: O(n³). For n = 5,000 that is about 2 × 10¹⁰, plus a sort and a hash for every answer.
The way in: fix the first number. If it is -1, you need two more numbers that add up to +1. That is Two Sum (episode 2), and on a sorted array, Two Sum has a trick that needs no hash map.
Two pointers on a sorted array
Picture a shelf of price tags sorted from cheapest to costliest. You want two items that cost exactly 10 together.
- Left hand on the cheapest, right hand on the costliest. Add the prices.
- Too cheap? The cheapest item can't be in any answer, even with the costliest partner. Move the left hand right.
- Too costly? The costliest item can't be in any answer, even with the cheapest partner. Move the right hand left.
- Each step throws one item away for good, so one walk, O(n), finds the pair.
import java.util.*;
public class Main {
public static void main(String[] args) {
int[] a = {1, 3, 4, 6, 8, 11};
int target = 10, lo = 0, hi = a.length - 1;
while (lo < hi) {
int sum = a[lo] + a[hi];
if (sum == target) {
System.out.println(a[lo] + " + " + a[hi]);
break;
}
if (sum < target) lo++;
else hi--;
}
}
}
Output:
4 + 6
The walk: 1 + 11 = 12 (too big, hi moves), 1 + 8 = 9 (too small, lo moves), 3 + 8 = 11 (hi moves), 3 + 6 = 9 (lo moves), 4 + 6 = 10. Five steps instead of fifteen pairs.
The key insight: 3Sum = a loop + two pointers
- Sort
nums. - For each
i, findlo,hiafteriwithnums[lo] + nums[hi] = -nums[i]using two pointers. - Sum below 0 →
lo++. Above 0 →hi--. Exactly 0 → record the triplet. - Duplicates sit side by side after sorting, so skip them: skip
iwhennums[i] == nums[i - 1], and after a hit moveloandhipast equal values.
Dry run: sorted [-4, -1, -1, 0, 1, 2]
| i (value) | lo, hi (values) | sum | action |
|---|---|---|---|
| 0 (-4) | -1, 2 | -3 | too small, lo++ |
| 0 (-4) | -1, 2 / 0, 2 / 1, 2 | -3, -2, -1 | too small each time, lo meets hi |
| 1 (-1) | -1, 2 | 0 | record [-1, -1, 2], move both |
| 1 (-1) | 0, 1 | 0 | record [-1, 0, 1], move both, pointers cross |
| 2 (-1) | same value as i = 1: skip | ||
| 3 (0) | 1, 2 | 3 | too big, hi--, pointers meet |
Answer: [[-1, -1, 2], [-1, 0, 1]], each exactly once, with no HashSet.
The optimal solution
import java.util.*;
public class Main {
static List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
int lo = i + 1, hi = nums.length - 1;
while (lo < hi) {
int sum = nums[i] + nums[lo] + nums[hi];
if (sum < 0) lo++;
else if (sum > 0) hi--;
else {
res.add(Arrays.asList(nums[i], nums[lo], nums[hi]));
while (lo < hi && nums[lo] == nums[lo + 1]) lo++;
while (lo < hi && nums[hi] == nums[hi - 1]) hi--;
lo++;
hi--;
}
}
}
return res;
}
public static void main(String[] args) {
System.out.println(threeSum(new int[]{-1, 0, 1, 2, -1, -4}));
System.out.println(threeSum(new int[]{0, 0, 0, 0}));
System.out.println(threeSum(new int[]{0, 1, 1}));
System.out.println(threeSum(new int[]{-2, 0, 1, 1, 2}));
}
}
Output:
[[-1, -1, 2], [-1, 0, 1]]
[[0, 0, 0]]
[]
[[-2, 0, 2], [-2, 1, 1]]
On the 5,000 entries that timed out:
long t = System.nanoTime();
int found = threeSum(nums).size();
System.out.println(found + " triplets " + (System.nanoTime() - t) / 1000000 + " ms");
Output (the time varies from run to run):
416024 triplets 234 ms
The same solution in C++ and Python
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> threeSum(vector<int> nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> res;
int n = nums.size();
for (int i = 0; i + 2 < n; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
int lo = i + 1, hi = n - 1;
while (lo < hi) {
int sum = nums[i] + nums[lo] + nums[hi];
if (sum < 0) lo++;
else if (sum > 0) hi--;
else {
res.push_back({nums[i], nums[lo], nums[hi]});
while (lo < hi && nums[lo] == nums[lo + 1]) lo++;
while (lo < hi && nums[hi] == nums[hi - 1]) hi--;
lo++; hi--;
}
}
}
return res;
}
int main() {
for (auto& t : threeSum({-1, 0, 1, 2, -1, -4}))
cout << "[" << t[0] << ", " << t[1] << ", " << t[2] << "]\n";
}
Output: [-1, -1, 2] and [-1, 0, 1], one per line. (i + 2 < n avoids the unsigned trap of nums.size() - 2 when the vector is short.)
def three_sum(nums):
nums = sorted(nums)
res, n = [], len(nums)
for i in range(n - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue
lo, hi = i + 1, n - 1
while lo < hi:
s = nums[i] + nums[lo] + nums[hi]
if s < 0:
lo += 1
elif s > 0:
hi -= 1
else:
res.append([nums[i], nums[lo], nums[hi]])
while lo < hi and nums[lo] == nums[lo + 1]:
lo += 1
while lo < hi and nums[hi] == nums[hi - 1]:
hi -= 1
lo += 1
hi -= 1
return res
print(three_sum([-1, 0, 1, 2, -1, -4])) # [[-1, -1, 2], [-1, 0, 1]]
print(three_sum([0, 0, 0, 0])) # [[0, 0, 0]]
Complexity
| Approach | Time | Extra space | n = 5,000 |
|---|---|---|---|
| Three loops + HashSet | O(n³) | O(answers) | Time Limit Exceeded |
| Sort + two pointers | O(n log n + n²) = O(n²) | O(1) besides the output and the sort | milliseconds |
No algorithm is known that is much faster than O(n²) for 3Sum in general, so O(n²) is the expected interview answer.
Common mistakes
| Mistake | What you see | Why | Fix |
|---|---|---|---|
if (nums[i] == nums[i + 1]) continue; |
[[-1, 0, 1]]: [-1, -1, 2] is lost |
skips the first of equal values, the only i that can use both | if (i > 0 && nums[i] == nums[i - 1]) continue; |
| No skip after a hit | [[-2, 0, 2], [-2, 0, 2]] for [-2, 0, 0, 2, 2] |
lo and hi land on equal values again | skip equal lo and hi, then move both |
| Three loops, no sort of the triplet | [-1, 0, 1] and [0, 1, -1] |
same group, other order | sort, then skip duplicates |
| Two pointers on an unsorted array | missing triplets | moving a pointer only throws away useless values when the array is sorted | Arrays.sort(nums) first |
nums.size() - 2 in C++ on a short vector |
huge loop, crash | size() is unsigned: 1 - 2 wraps around |
write i + 2 < n with int n |
Mini project: the auditor's report
Read a list of ledger entries (positive and negative rupee amounts) and print every group of three that cancels out, formatted like +500, -300, -200. Then extend it to groups of four (4Sum): fix two numbers with two loops, two-pointer the rest, and skip duplicates at every level. Try it on [1, 0, -1, 0, -2, 2], which has three groups of four: [-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1].
Practice
- 3Sum Closest (LeetCode 16): the triplet sum closest to
target = 1in[-1, 2, 1, -4].
Solution
Same loop + two pointers, but keep the sum with the smallest |sum - target|, moving lo when sum < target and hi otherwise. Answer: 2 (-1 + 2 + 1).
- Two Sum II (LeetCode 167): sorted
[2, 7, 11, 15], target 9. Return the 1-based positions.
Solution
Two pointers from both ends: 2 + 15 too big, 2 + 11 too big, 2 + 7 = 9. Answer: [1, 2], O(n) time, O(1) space.
- Count the triplets with sum less than 2 in
[-2, 0, 1, 3](LeetCode 259).
Solution
Sort, fix i, two pointers: when nums[i] + nums[lo] + nums[hi] < target, every hi' between lo + 1 and hi also works, so add hi - lo and move lo; otherwise move hi. Answer: 2 ([-2, 0, 1], [-2, 0, 3]).
- Why does the outer loop stop at
nums.length - 2?
Solution
lo = i + 1 and hi = n - 1 must be two more distinct positions, so i can be at most n - 3.
Quick quiz
What does threeSum(new int[]{-2, -2, 0, 2, 4, -4}) return?
- 1 triplet
- 2 triplets
- 3 triplets
- 4 triplets
Answer
3 triplets. Sorted: -4, -2, -2, 0, 2, 4. The program prints [[-4, 0, 4], [-2, -2, 4], [-2, 0, 2]]. [-4, 2, 2] is not allowed: there is only one 2.
Interview questions
- Why sort first? Sorting makes the two-pointer moves safe (too small → the smallest is useless) and puts duplicates next to each other so they can be skipped.
- Prove the two-pointer step is safe. If
nums[lo] + nums[hi]is too small, thennums[lo]plus any value at or beforehiis also too small, solocan be discarded. The mirror argument works forhi. - How do you avoid duplicate triplets without a HashSet? Skip
iwhen it equalsnums[i - 1], and after each hit, advanceloandhipast equal values. - Time and space? O(n²) time; O(1) extra space apart from the output (Java's
Arrays.sortonint[]uses O(log n) stack). - Generalize to kSum. Recursively fix one number and solve (k-1)Sum on the rest; the base case is two pointers. Time O(n^(k-1)).
Glossary
| Term | Meaning |
|---|---|
| Triplet | A group of three values taken from three different positions |
| Unique triplets | No two triplets with the same three values, in any order |
| Two pointers | Two indexes that move through an array (here, from both ends towards each other) |
| Sorted array | Values in non-decreasing order; required for the two-pointer moves |
| Duplicate skip | Moving past equal neighbours so each value is tried once in each role |
Arrays.asList |
Java: makes a fixed-size List from values |
HashSet |
A set that stores each distinct element once, with O(1) average lookups |
| O(n log n) | The cost of sorting n items with a good sorting algorithm |
| kSum | The general problem: k numbers that add up to a target |
Summary
- Three loops are O(n³) and repeat triplets in different orders.
- Two pointers on a sorted array find a pair with a given sum in O(n): too small → move left up, too big → move right down.
- 3Sum = sort, then for each
i, two pointers on the rest for-nums[i]. - Skip
nums[i] == nums[i - 1], and skip equallo/hiafter a hit. O(n²) time, O(1) extra space.
Next episode: Container With Most Water.