Three Number Sum is where the two-pointer technique stops being a curiosity and becomes the tool. On Two Number Sum a hash set beats it. Here it wins outright, because sorting buys three separate things at once and no hash-based approach gets all three.
The problem
Given a non-empty array of distinct integers and a target sum, find every triplet that sums to the target. Each triplet must be in ascending order, and the triplets themselves ordered ascending. Return an empty list if there are none.
array = [12, 3, 1, 2, -6, 5, -8, 6], target = 0
-> [[-8, 2, 6], [-8, 3, 5], [-6, 1, 5]]
array = [1, 2, 3], target = 100 -> []The ordering requirement is a hint in disguise. It is telling you the expected solution sorts the array — because once sorted, both orderings come out for free rather than needing a sort at the end.
Fix one, then two-point the rest
A triplet is a pair plus one more number. So walk the array, treat each element as the
anchor, and look for a pair in the remainder that sums to
target - anchor. That inner search is exactly Two Number Sum on a sorted array, which is
the O(n) two-pointer scan.
Sorting first is what makes it work, and it pays for itself three times:
- Two pointers become valid — a sum that is too small can only be fixed by moving
leftright, too large by movingrightleft. - Each triplet emerges already in ascending order.
- Anchors are visited in ascending order, so the list of triplets is sorted too.
The anchor loop stops at size - 2, because an anchor needs at least two elements to
its right to form a triplet at all.
Java
public static List<List<Integer>> threeNumberSum(int[] array, int targetSum) {
List<List<Integer>> triplets = new ArrayList<>();
if (array.length < 3) { // 3, not 2 — a triplet needs three numbers
return triplets;
}
Arrays.sort(array); // note: this reorders the CALLER's array
for (int i = 0; i < array.length - 2; i++) {
int left = i + 1; // only look to the RIGHT of the anchor,
int right = array.length - 1; // so no triplet is found twice
while (left < right) {
int sum = array[i] + array[left] + array[right];
if (sum == targetSum) {
triplets.add(List.of(array[i], array[left], array[right]));
left++; // both, not one: see below
right--;
} else if (sum < targetSum) {
left++; // need a bigger number
} else {
right--; // need a smaller number
}
}
}
return triplets;
}Return List<List<Integer>>, not List<Integer[]>.
Java arrays use identity equality, so two Integer[] holding the same values are not
equals. That makes the result awkward to assert on in a test, impossible to put in a
Set, and it prints as [Ljava.lang.Integer;@1b6d3586. A List
has value equality and a readable toString, and costs nothing.
Why both pointers move after a hit
This is the line worth being able to justify. Once array[left] + array[right] hits
the target for this anchor, moving only left makes the sum strictly larger, and moving
only right makes it strictly smaller — neither can produce another hit against the same
anchor. Since the values are distinct, there is exactly one partner for each, so advancing both is
correct and skips a pointless comparison.
Python
def three_number_sum(array: list[int], target_sum: int) -> list[list[int]]:
if len(array) < 3:
return []
array.sort() # sorts the caller's list in place
triplets = []
for i in range(len(array) - 2):
left, right = i + 1, len(array) - 1
while left < right:
total = array[i] + array[left] + array[right]
if total == target_sum:
triplets.append([array[i], array[left], array[right]])
left += 1
right -= 1
elif total < target_sum:
left += 1
else:
right -= 1
return tripletsarray.sort() reorders the caller's list. Use array = sorted(array) if
that is not acceptable — same trade as Java's clone(), costing O(n)
space.
Complexity
O(n²) time: O(n log n) to sort, then n anchors each running
an O(n) two-pointer scan. The sort disappears into the square. Space is
O(1) beyond the output — the two-pointer scan allocates nothing.
O(n²) is also the floor. The output alone can hold O(n²) triplets, so no
algorithm can do better in the worst case. Saying that is a stronger answer than just quoting the
runtime, because it shows the bound is not a limitation of your approach.
Why not a hash set
You can fix an anchor and run the O(n) hash-set version of Two Number Sum on the
rest. Same O(n²) time, but it costs O(n) space, it does not produce sorted
triplets, and — the real problem — it will report the same triplet more than once whenever the input
allows it, so you need a Set of canonicalised triplets on top. The two-pointer version
avoids all of that by construction.
The version with duplicates
This problem guarantees distinct integers, and that guarantee is doing a lot of work. LeetCode 15, 3Sum is the same problem without it, and the difference is not small — with repeated values, both the anchor loop and the two-pointer scan will emit the same triplet several times, so two separate skip rules are needed:
// Only needed when values may repeat.
if (i > 0 && array[i] == array[i - 1]) continue; // same anchor as last round
// ...and after recording a hit, step past runs of equal values:
while (left < right && array[left] == array[left + 1]) left++;
while (left < right && array[right] == array[right - 1]) right--;Ask which version you are being given. If the answer is "duplicates are possible", the code above is incomplete and you need those three lines.
What the interviewer is checking
- That you sort first, and can name all three things sorting buys.
- That
leftstarts ati + 1, so a triplet is never found twice and the anchor is never reused. - That you can justify moving both pointers after a hit.
- That the guard is
< 3, and the loop boundsize - 2. - That you notice sorting mutates the input.
- That you asked about duplicates — and know what changes if they are allowed.
- That
O(n²)is the floor, because the output can be that large.