The 3Sum task takes an array of integers and a target value, then returns every value triple whose three numbers add to that target. Each triple must be unique by value, so the same combination is returned once even when duplicate indices can form it.
The efficient approach sorts the array, fixes one number, and scans the remaining range with two pointers. It reduces the search from cubic time to O(n²), while duplicate skipping preserves the output contract.
What Does 3Sum Return?
Define the input, target, and output contract
Given an integer array nums and an integer target, return a list of triples [a, b, c] such that a + b + c = target. The order inside a triple is normally ascending, and the result can be empty when no combination qualifies.
Require value-unique triples, not index-unique matches
Uniqueness applies to values rather than positions. For example, an array containing several copies of -1 must not produce [-1, 0, 1] repeatedly merely because different copies occupy different indices. Sorting makes those repeated values adjacent, which makes them easy to skip.
Why Is the Three-Sum Problem Expensive to Brute Force?
Count the cubic search space
The direct solution tests every combination of three indices. With n values, that is roughly n × (n – 1) × (n – 2) / 6 checks, or O(n³) time. Each check adds three values and compares the sum with the target.
Use brute force as a correctness baseline
Brute force is useful for small inputs and test validation because its logic is straightforward. For production-sized arrays, the cubic growth becomes expensive. A set can remove duplicate outputs, but it does not eliminate the cost of examining nearly every triple.
How the 3Sum algorithm Uses Sorting and Two Pointers
Sort the array and fix one value
Sort nums in ascending order. For each index i, treat nums[i] as the first value, set left = i + 1, and set right to the final index. The remaining task is a two-sum search for target – nums[i].
Move pointers based on the current sum
- If the three-value sum is too small, increase left to make the sum larger.
- If the sum is too large, decrease right to make the sum smaller.
- If the sum matches, record the triple, then move both pointers inward.
Walk through [-4, -1, -1, 0, 1, 2] with target 0
Start with -4. The pointers begin at -1 and 2, producing -3, so move left rightward. The next sums are -3, -2, and -1; each is too small, so left continues forward until the scan ends.
Next, fix -1 at index 1. With the second -1 and 2, the sum is 0, so record [-1, -1, 2]. Move both pointers: 0 and 1 also produce 0, so record [-1, 0, 1]. The next pointer positions cross. The second -1 at index 2 is skipped because it repeats the fixed value. The final result contains those two triples.
Implement the sorted scan
- Sort the input array.
- Loop through each possible first index while at least two values remain.
- Skip the current index when its value equals the previous fixed value.
- Use left and right pointers, calculate the sum, and move the appropriate pointer.
- After recording a match, advance past equal left values and retreat past equal right values.
How Does Duplicate Skipping Affect Complexity?
Skip repeated fixed values and pointer values
Before each scan, skip a fixed value that equals the value at the preceding index. After finding a match, move left past every identical value and move right past every identical value. This prevents duplicate triples without relying on a set.
Compare O(n²) time with sorting and extra-space costs
Sorting costs O(n log n). The outer loop and two-pointer scans cost O(n²), so the complete algorithm remains O(n²). An in-place sort uses O(1) auxiliary space apart from the output; copying the array first adds O(n) space. The returned triples require additional output space proportional to their number.