15. 3Sum

3Sum is where a lot of people first hit a wall — not because the two-pointer scan is hard, but because returning only the distinct triplets is fiddly. Sort the array first, and the whole thing collapses into a problem you already know.

Question

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

• Example1

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

Output:
[[-1,-1,2],[-1,0,1]]

Explanation: 
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.

The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

• Example2

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.

• Example3

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.

• Constraints
  • $3 <= nums.length <= 3000$
  • $-10^5 <= nums[i] <= 10^5$

Approach: sort, then fall back to Two Sum

Once the array is sorted, fix the leftmost number nums[i] and what’s left is a familiar problem: find two numbers in the rest of the array that add up to -nums[i]. That’s Two Sum — and on a sorted array you can solve it in one pass with two pointers instead of a hash map. Walk left up from i + 1 and right down from the end, and let the running sum tell you which way to move: too big, pull right in; too small, push left out.

Sorting is what unlocks that scan, and it hands you two cheap prunings on the way:

• Once nums[i] > 0, every remaining number is positive too, so no triplet can reach 0 — break out entirely.

• If nums[i] == nums[i - 1], this element already started an identical search, so continue.

• Why ArrayList instead of LinkedList?

  • I prefer ArrayList over LinkedList because ArrayList offers better cache locality and faster iteration performance.
  • In this problem, we mainly append elements and iterate through the result list, and we don’t perform frequent insertions or deletions in the middle. Therefore, ArrayList is more efficient and is generally the preferred choice in practice.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public List<List<Integer>> threeSum(int[] nums) {

    List<List<Integer>> result = new ArrayList<>();
    if (nums == null || nums.length < 3) {
        return result;
    }

    Arrays.sort(nums);

    for (int i = 0; i < nums.length - 2; i++) {
        if (nums[i] > 0) {
            break;
        }

        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }

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

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

            if (sum == 0) {
                result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                left++;
                right--;

                while (left < right && nums[left] == nums[left - 1]) {
                    left++;
                }
                while (left < right && nums[right] == nums[right + 1]) {
                    right--;
                }
            } else if (sum > 0) {
                right--;
            } else {
                left++;
            }
        }
    }

    return result;
}

The three places duplicates sneak in

“The solution set must not contain duplicate triplets” is the line that actually makes 3Sum a medium. There are exactly three spots to guard, and the code hits each one:

1. The outer index — if (i > 0 && nums[i] == nums[i - 1]) continue; stops the same smallest value from launching two identical searches.
2. The left pointer after a match — while (nums[left] == nums[left - 1]) left++; skips repeated values so [-1,0,1] isn’t emitted twice.
3. The right pointer after a match — the mirror of the above.

Each guard closes a gap the others don’t. Drop the outer one on an input like [-2,-2,0,2,4] and [-2,0,2] comes out twice — once for each leading -2 starting the same search; drop a pointer skip and an input with adjacent equals on that side doubles up the same way. Not every input exercises all three, but leave one out and some input will slip a duplicate through. Because the array is sorted, equal values sit next to each other, so each guard is just a cheap “same as my neighbor?” check instead of a set lookup.

Complexity

Step	Cost
Sort	$O(n \log n)$
Outer loop × two-pointer scan	$O(n^2)$
Total time	$O(n^2)$
Extra space	$O(\log n)$ for the sort’s stack, beyond the output

The $O(n^2)$ scan dominates, so the sort is effectively free. You can’t beat $O(n^2)$ in the general case anyway — the output alone can hold on the order of $n^2$ triplets, and you have to write every one.

Step through the sort-and-scan below to watch the pointers move and the duplicate skips fire:

If you can do this, 4Sum is just one more loop

The reduction stacks. 4Sum fixes two indices and runs the same two-pointer scan inside, for $O(n^3)$; the duplicate-skip logic is identical, just applied at one more level. Nail the three skip-checks here and the whole k-Sum family stops being intimidating — it’s always “sort, fix the outer values, two-pointer the rest, skip neighbors.”

References

• https://leetcode.com/problems/3sum/