Generated by Codex with GPT-5

Quick facts

• Difficulty: MEDIUM
• Problem: 3Sum
• Main tags: Array, Two Pointers, Sorting

What the problem is really asking

The input is an integer array, and the goal is to return every unique triplet whose values add up to 0.

Two details make the problem harder than it looks:

• the output needs all valid triplets, not just one
• duplicate triplets are not allowed, even if the same values can be picked from different indices

So the real challenge is not just finding three numbers that sum to zero. It is finding all distinct value combinations without repeating work.

Why the obvious approach is too slow

The brute-force idea is simple:

• choose the first index
• choose the second index
• choose the third index
• check whether the three values sum to 0

That works, but it costs O(n^3) time. For interview-sized inputs, that is too slow.

A natural improvement is to fix one number and turn the rest of the problem into a 2Sum search. That gets much closer, but duplicate handling still becomes messy unless the array is organized first.

The key insight

Sorting changes the problem from “search everywhere” into “move with direction.”

After sorting:

• pick one value as the first number in the triplet
• use two pointers to search the rest of the array for two numbers that sum to the opposite value

If the current three-number sum is too small, the left pointer must move right to increase it.

If the current sum is too large, the right pointer must move left to decrease it.

That monotonic behavior is exactly what makes the two-pointer scan efficient.

Sorting also makes duplicate control much easier:

• skip a starting value if it is the same as the previous starting value
• after finding a valid triplet, move past repeated left and right values so the same triplet is not emitted again

How to derive the optimal solution

One clean way to derive the final algorithm is:

1. Start with brute force and notice the only hard requirement is uniqueness.
2. Fix one number, which reduces the remaining search to finding a pair that hits a target.
3. Sort the array so pair-search can use two pointers instead of a nested scan.
4. Add duplicate skipping in the sorted array so each value combination is produced once.

That gives the standard optimal approach for this problem:

• Time: O(n^2)
• Extra space: O(1) beyond the output if sorting in place is allowed

The sort itself costs O(n log n), but the O(n^2) search dominates for large inputs.

Best approaches

The sorted two-pointer solution is the best default because it is both optimal and easy to reason about.

There is also a hash-set style approach that fixes one value and solves 2Sum with a set for the remainder. That can also reach O(n^2) time, but duplicate handling is more awkward and the space usage is higher.

For this LeetCode problem, sorting plus two pointers is the cleanest version to remember and implement.

Python solution

from typing import List


def find_zero_sum_triplets(numbers: List[int]) -> List[List[int]]:
    """Return all unique triplets whose values sum to zero."""
    sorted_numbers = sorted(numbers)
    zero_sum_triplets: List[List[int]] = []

    for first_index in range(len(sorted_numbers) - 2):
        first_value = sorted_numbers[first_index]

        # Reusing the same starting value would only create duplicate triplets.
        if first_index > 0 and first_value == sorted_numbers[first_index - 1]:
            continue

        # Once the smallest remaining value is already positive, the total
        # can no longer reach zero because the array is sorted.
        if first_value > 0:
            break

        _collect_matching_pairs(
            sorted_numbers=sorted_numbers,
            first_index=first_index,
            triplets=zero_sum_triplets,
        )

    return zero_sum_triplets


def _collect_matching_pairs(
    sorted_numbers: List[int],
    first_index: int,
    triplets: List[List[int]],
) -> None:
    target_pair_sum = -sorted_numbers[first_index]
    left_index = first_index + 1
    right_index = len(sorted_numbers) - 1

    while left_index < right_index:
        left_value = sorted_numbers[left_index]
        right_value = sorted_numbers[right_index]
        current_pair_sum = left_value + right_value

        if current_pair_sum < target_pair_sum:
            left_index += 1
            continue

        if current_pair_sum > target_pair_sum:
            right_index -= 1
            continue

        triplets.append(
            [sorted_numbers[first_index], left_value, right_value]
        )

        left_index += 1
        right_index -= 1

        # Skip repeated values so each triplet is emitted once.
        while left_index < right_index and sorted_numbers[left_index] == sorted_numbers[left_index - 1]:
            left_index += 1
        while left_index < right_index and sorted_numbers[right_index] == sorted_numbers[right_index + 1]:
            right_index -= 1


class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        return find_zero_sum_triplets(nums)

Why this works

For each fixed first value, the two pointers search all remaining pairs in sorted order.

Because the array is sorted, moving the left pointer always increases the pair sum, and moving the right pointer always decreases it. That means no pair needs to be revisited.

When the pair sum matches the target, the algorithm has found a valid triplet. After recording it, it skips repeated neighboring values so that the same value combination is not added again.

So the algorithm is complete because it explores every relevant pair for every starting value, and it is correct because sorting makes the pointer movements logically safe.

Practical takeaway

This problem looks like a three-number search problem, but the best way to think about it is:

• sort first
• fix one number
• solve the rest as a duplicate-aware two-pointer 2Sum

That reframing turns an intimidating O(n^3) search into a structured O(n^2) pattern that shows up in many other array problems.