3Sum

Step 01

Brute Force — Triple Nested Loops

The most obvious approach: try every combination of three distinct indices and check if they sum to zero. We also need a set to discard duplicate triplets.

Naive O(n³) Approach

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)
                result.add(sorted(i, j, k));

For an array of length 3000 (a typical LeetCode constraint), this examines ~4.5 billion triplets. That's a guaranteed Time Limit Exceeded.

Why it fails

O(n³)

Time complexity

TLE

n = 3000 is way too slow

💡

Can we do better? The 2Sum problem uses a hash map to go from O(n²) to O(n). What if we fix one number and solve 2Sum on the rest? That would give us O(n) × O(n) = O(n²). But there's an even cleaner way — sort first, then use two pointers.

Step 02

The Core Insight — Sort + Two Pointers

Sort the array first. Then for each element nums[i], we need to find two numbers in the remaining subarray that sum to -nums[i]. Since the array is sorted, we can use two pointers converging from both ends.

The Strategy

1

Sort the array

Enables two-pointer technique and makes duplicate skipping trivial.

2

Fix one number (outer loop)

Iterate i from index 0. We need nums[left] + nums[right] = -nums[i].

3

Two pointers converge

left starts at i+1, right starts at end. If sum < 0, move left up. If sum > 0, move right down.

4

Skip duplicates

After finding a triplet, advance both pointers past identical values to avoid duplicates in the output.

⚡

Why does sorting help so much? In a sorted array, the two-pointer technique guarantees we visit each pair at most once: if the sum is too small, the only way to increase it is to move the left pointer right. If too large, move the right pointer left. No backtracking needed.

Step 03

Algorithm Walkthrough

Let's trace through the example [-1, 0, 1, 2, -1, -4]. After sorting, we get:

Sorted Array

-4

-1

0

1

2

Indices: 0 through 5. Now we fix each element and use two pointers on the rest.

Iteration: i = 0, fix nums[0] = -4

Target for two pointers: -(-4) = 4. We need left + right = 4.

-4fix

-1L

-1

0

1

2R

-1 + 2 = 1 < 4. Sum is too small, so move L right. After several steps, L and R cross without finding sum = 4. No triplets with -4.

Iteration: i = 1, fix nums[1] = -1

Target: -(-1) = 1. We need left + right = 1.

-4

-1fix

-1L

0

1

2R

            sum = -1 + 2 = 1 = target!
          

Found: [-1, -1, 2]

-4

-1fix

-1

0L

1R

2

            sum = 0 + 1 = 1 = target!
          

Found: [-1, 0, 1]

After this, L and R cross. Move to next fixed element.

Iteration: i = 2, nums[2] = -1 — Skip!

-4

-1

0

1

2

nums[2] == nums[1], so we skip this iteration entirely to avoid generating the same triplets we already found. This is the outer duplicate check.

Final Result

[-1, -1, 2]

[-1, 0, 1]

Step 04

Handling Duplicates

Avoiding duplicate triplets is the trickiest part. There are three places where we must skip:

Three Duplicate Checks

Outer loop: skip same fixed value

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

If the fixed element is the same as the previous one, all triplets would be duplicates. Skip it.

Left pointer: skip duplicates after match

while (left < right && nums[left] == nums[left+1]) left++;

After finding a valid triplet, advance left past all identical values.

Right pointer: skip duplicates after match

while (left < right && nums[right] == nums[right-1]) right--;

Similarly, advance right past identical values from the other end.

💡

Why three checks, not just a Set? Using a Set to de-duplicate works, but it adds O(n) space and hash overhead. The three skip checks are O(1) each and keep space at O(1) (excluding output). Since the array is sorted, identical values are adjacent — a simple comparison with the neighbor is all we need.

Step 05

Edge Cases

Make sure your solution handles these correctly:

All Zeros

[0, 0, 0]

Output: [[0, 0, 0]] — exactly one triplet. Duplicate skipping must not skip the only valid answer.

No Valid Triplets

[1, 2, 3]

Output: [] — all positive, no way to sum to zero.

Many Duplicates

[-1, -1, -1, 2, 2, 2]

Output: [[-1, -1, 2]] — only one unique triplet despite 9 possible (i,j,k) combinations.

Minimum Length

[1, -1]

Output: [] — fewer than 3 elements means no triplet is possible. The outer loop condition i < n-2 handles this.

⚡

Early exit optimization: If after sorting, nums[i] > 0, we can break the outer loop. All remaining elements are positive, so no three positive numbers can sum to zero.

Step 06

Full Annotated Code

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

        // Step 1: Sort — enables two-pointer and duplicate skipping
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();

        for (int i = 0; i < nums.length - 2; i++) {

            // Skip duplicate fixed elements
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            // Early exit: if nums[i] > 0, no solution possible
            if (nums[i] > 0) break;

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

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

                if (sum == 0) {
                    // Found a valid triplet!
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));

                    // Skip duplicates on the left
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    // Skip duplicates on the right
                    while (left < right && nums[right] == nums[right - 1]) right--;

                    // Move both inward to search for more triplets
                    left++;
                    right--;

                } else if (sum < 0) {
                    left++;   // Need a larger sum → move left right
                } else {
                    right--;  // Need a smaller sum → move right left
                }
            }
        }
        return result;
    }
}

Step 07

Interactive Demo

Enter an array and watch the two-pointer algorithm find all triplets step by step.

⚙ 3Sum Visualizer

nums

Step 08

Complexity Analysis

Time

O(n²)

Space

O(1)*

Breakdown

Sorting: O(n log n)

Dominated by the quadratic term, so it doesn't affect overall complexity.

Outer loop: O(n) iterations

We fix each element once. The duplicate skip only reduces iterations.

Inner two pointers: O(n) each

Left and right each traverse at most n elements per outer iteration, converging toward each other.

Total: O(n log n) + O(n) × O(n) = O(n²).

Space is O(1) excluding the output list. The sort is in-place and we only use a few pointer variables. Some implementations of sorting use O(log n) stack space, but the algorithm itself requires no auxiliary data structures.

📝

Can we beat O(n²)? No. It's been proven that 3Sum has a lower bound of Omega(n²) in the comparison-based model. Our solution is asymptotically optimal.

Roadmap