Three Sum Problem: Find All Triplets With a Given Sum

Given an array of integers and a target, find every unique triplet that sums to the target. The algorithm is a sorted two-pointer scan and it is short. What makes this problem worth working through carefully is that the naive version returns the right triplets several times each, and removing the duplicates is three separate conditions in three separate places.

The problem

Input:  nums = [-1, 0, 1, 2, -1, -4], target = 0
Output: [[-1, -1, 2], [-1, 0, 1]]

Note what is not in the output. [-1, 0, 1] can be formed from two different pairs of indices — the array holds two -1 values, and it appears once. That is the whole difficulty.

Brute force, and what it costs

static List<List<Integer>> bruteForce(int[] nums, int target) {
    Set<List<Integer>> found = new HashSet<>();
    for (int i = 0; i < nums.length - 2; i++) {
        for (int j = i + 1; j < nums.length - 1; j++) {
            for (int k = j + 1; k < nums.length; k++) {
                if (nums[i] + nums[j] + nums[k] == target) {
                    List<Integer> triplet = new ArrayList<>(List.of(nums[i], nums[j], nums[k]));
                    Collections.sort(triplet);
                    found.add(triplet);
                }
            }
        }
    }
    return new ArrayList<>(found);
}

O(n³), and the HashSet of sorted triplets is doing the deduplication. It works, and it is worth writing once because it is the reference the fast version must agree with.

Sorting unlocks two pointers

Sort the array. Fix the first element, then find pairs in the remainder that sum to target - nums[i], and because the remainder is sorted, that search is a linear scan from both ends rather than another nested loop.

static List<List<Integer>> threeSum(int[] nums, int target) {
    Arrays.sort(nums);
    List<List<Integer>> result = new ArrayList<>();

    for (int i = 0; i < nums.length - 2; i++) {
        // (1) skip a repeated first element
        if (i > 0 && nums[i] == nums[i - 1]) continue;

        int left = i + 1, right = nums.length - 1;

        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];

            if (sum == target) {
                result.add(List.of(nums[i], nums[left], nums[right]));

                // (2) skip repeats on the left
                while (left < right && nums[left] == nums[left + 1]) left++;
                // (3) skip repeats on the right
                while (left < right && nums[right] == nums[right - 1]) right--;

                left++;
                right--;
            } else if (sum < target) {
                left++;              // need a larger sum
            } else {
                right--;             // need a smaller sum
            }
        }
    }
    return result;
}

O(n²) time, an outer loop over n with a linear inner scan, and O(1) extra space beyond the output, or O(log n) counting the sort’s stack.

Why the pointer moves are correct

At any moment left and right bracket the candidate pairs. If the sum is too small, no pair using the current right and a smaller left can help, every such pair is smaller still, so left must increase. If the sum is too large, right must decrease by the mirror argument.

That is why sorting is not a convenience here: it is what makes “too small” imply a direction. On unsorted input a comparison tells you nothing about where to look next.

The three duplicate skips

Each one prevents a different repetition, and they are not interchangeable.

(1) The outer skip stops the same first element being used as an anchor twice. In [-1, -1, 0, 1, 2] the second -1 would generate the identical set of triplets the first already did.

(2) and (3) the inner skips run only after a match is recorded. Once [-1, 0, 1] is found, any further 0 at left paired with a further 1 at right produces the same triplet, so both pointers advance past their runs.

The left < right guard inside each inner while is not decoration. Without it, an array such as [0, 0, 0, 0] walks left past right and the outer loop then reads inverted indices.

Then left++ and right-- after the skips. Moving only one pointer after a match is a common bug: the sum is now guaranteed to miss on that side, so the loop wastes an iteration and, worse, can re-find the same triplet if the skip conditions did not fire.

The hash-set alternative

Fixing the first element and using a set for the inner pair is also O(n²), and it avoids sorting:

static Set<List<Integer>> threeSumHashing(int[] nums, int target) {
    Set<List<Integer>> result = new HashSet<>();

    for (int i = 0; i < nums.length - 2; i++) {
        Set<Integer> seen = new HashSet<>();
        for (int j = i + 1; j < nums.length; j++) {
            int need = target - nums[i] - nums[j];
            if (seen.contains(need)) {
                List<Integer> triplet = new ArrayList<>(List.of(nums[i], nums[j], need));
                Collections.sort(triplet);
                result.add(triplet);
            }
            seen.add(nums[j]);
        }
    }
    return result;
}

Same asymptotic cost, O(n) extra space, and the deduplication is delegated to the outer Set rather than reasoned about. It is easier to get right and slower in practice. Hashing plus sorting each triplet is a large constant next to two array reads.

Worth knowing for the case where the input must not be reordered, which is the real reason to choose it.

Values or indices?

The two-pointer solution returns values, and it cannot return indices, because sorting destroys the original positions.

If the problem asks for indices, the sort has to carry them:

Integer[] idx = IntStream.range(0, nums.length).boxed().toArray(Integer[]::new);
Arrays.sort(idx, Comparator.comparingInt(i -> nums[i]));

At which point the duplicate-skipping logic changes meaning too: two triplets with the same values at different indices are now different answers, so the skips must be removed. Read the problem statement before choosing; the two variants share an algorithm and not a solution.

Tracing the duplicate skips

On nums = [-4, -1, -1, 0, 1, 2] (already sorted) with target 0:

i	nums[i]	left	right	sum	action
0	−4	1	5	−3	too small, left++
0	−4	2	5	−3	too small, left++
0	−4	3	5	−2	too small, left++
0	−4	4	5	−1	too small, left++ — pointers meet, i++
1	−1	2	5	0	record [−1, −1, 2], skips, left=3 right=4
1	−1	3	4	0	record [−1, 0, 1], left=4 right=3, loop ends
2	−1	—	—	—	skipped by (1) — same as i=1

Row 7 is the outer skip earning its place: without it, i = 2 reproduces [-1, 0, 1] exactly. And the two records at i = 1 show why the inner skips are conditional on a match — they run only after something is added, never on the too-small and too-large branches, where advancing past a run would skip valid pairs.

Edge cases worth testing

• Fewer than three elements — the loop bounds handle it, but only because of the - 2.
• All zeros with target zero: [0,0,0,0] → exactly one triplet. This is the case the left < right guards exist for.
• No triplet at all → an empty list, not null.
• Integer overflow: three values near Integer.MAX_VALUE overflow int addition. Sum into a long if the input range permits it.

The last one is the one that survives review, because the test data never contains large values.

The shape underneath

Two Sum sorted plus an outer loop is Three Sum. Three Sum plus another outer loop is Four Sum, at O(n³). The general k-sum is a recursion that peels one index per level and bottoms out at the two-pointer scan.

Recognising that is worth more than the code: the same “sort, then collapse the inner search to a linear scan” move applies to closest-sum and smaller-than-target variants, which differ only in what they record when the pointers meet.

Related: the 0/1 knapsack problem for the other standard shape. More in the algorithms guides.

Frequently asked questions

Why sort first?

Sorting is what makes a comparison informative: if the sum is too small the only useful move is to increase the left pointer. On unsorted input there is no such direction.

What is the time complexity?

O(n²) — an outer loop with a linear two-pointer scan inside. The sort at O(n log n) is dominated by it.

How do I avoid duplicate triplets?

Three skips: one on the outer anchor before scanning, and two after recording a match, advancing past runs of equal values on each side.

Why does the inner skip need a left < right check?

Without it, an array such as [0,0,0,0] walks the pointers past each other and the next read uses inverted indices.

Why move both pointers after a match?

The sum is exact, so changing only one side guarantees a miss. Moving both keeps the scan making progress and avoids re-finding the same triplet.

Can I return indices instead of values?

Not from the sorted version — sorting destroys the positions. Sort an index array instead, and drop the duplicate skips, because equal values at different indices are then distinct answers.

Is the hash-set solution faster?

No. It is the same O(n²) with a larger constant and O(n) extra space. Its advantage is not reordering the input.

What about integer overflow?

Three values near Integer.MAX_VALUE overflow int addition. Sum into a long if the input range allows values that large.

How does this extend to Four Sum?

Another outer loop, giving O(n³), with the same duplicate skipping at each level. The general k-sum recurses down to the two-pointer base case.

What is the answer for [0,0,0,0] and target 0?

Exactly one triplet, [0,0,0]. It is the best single test case for the duplicate handling.