Generated by Codex with GPT-5

Quick facts

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

What the problem is really asking

The surface task is to return every unique quadruplet whose sum equals target.

The harder part is not the arithmetic. It is avoiding duplicate answers while still searching efficiently.

At a high level, the problem becomes much simpler after sorting:

• equal values become adjacent, so duplicates are easy to skip
• the remaining numbers are ordered, so two pointers can move intelligently
• the problem can be reduced step by step from 4Sum to 3Sum to 2Sum

That reduction is the key idea.

How to derive the standard solution

The easiest way to discover the right approach is to start from smaller versions of the same problem.

For 2Sum on a sorted array, two pointers work because:

• if the current sum is too small, moving the left pointer right is the only move that can increase it
• if the current sum is too large, moving the right pointer left is the only move that can decrease it

For 3Sum, a common pattern is:

1. Sort the array.
2. Fix one number.
3. Solve a 2Sum problem on the suffix.

4Sum is the same idea one level higher:

1. Sort the array.
2. Fix the first number.
3. Fix the second number.
4. Use two pointers to find the remaining pair.

That gives a clean O(n^3) solution, which is the standard optimal interview answer for returning all unique quadruplets.

Optimal solution

After sorting, scan the array with two nested loops:

• the first loop chooses the first value of the quadruplet
• the second loop chooses the second value
• the remaining suffix is searched with a left pointer and a right pointer

For each fixed pair:

1. Compute the four-number sum.
2. If the sum is too small, move the left pointer right.
3. If the sum is too large, move the right pointer left.
4. If the sum matches target, record the quadruplet and skip over any repeated values on both sides.

Two practical optimizations make the code cleaner and faster:

• Skip duplicate values in the first and second loops so the same quadruplet is never started twice.
• Use min/max pruning. If the smallest possible sum for the current prefix is already too large, break early. If the largest possible sum is still too small, skip that prefix immediately.

These optimizations do not change the big-O complexity, but they remove a lot of wasted work.

Why sorting matters so much

Sorting is doing almost all of the heavy lifting here.

Without sorting, the algorithm has no safe rule for moving pointers and no easy way to suppress duplicates. Once the numbers are ordered, both problems become manageable:

• duplicates are clustered together, so one comparison is enough to decide whether a value has already been used in the same position
• pointer movement becomes logically correct because larger values lie to the right and smaller values lie to the left

That is why this problem usually starts with sorting even though the final answer must be expressed in original values, not original indices.

Complexity

• Time: O(n^3) after sorting
• Extra space: O(n) in this Python version because sorted(nums) creates a new list, not counting the output

The sorting step costs O(n log n), but the cubic search dominates for larger inputs.

Python solution

from typing import Sequence


class FourSumSolver:
    """Return every unique quadruplet whose values add up to the target."""

    def solve(
        self,
        numbers: Sequence[int],
        target_sum: int,
    ) -> list[list[int]]:
        sorted_numbers = sorted(numbers)
        quadruplets: list[list[int]] = []
        total_numbers = len(sorted_numbers)

        if total_numbers < 4:
            return quadruplets

        for first_index in range(total_numbers - 3):
            first_value = sorted_numbers[first_index]

            # Skip duplicate starting values so each quadruplet is emitted once.
            if first_index > 0 and first_value == sorted_numbers[first_index - 1]:
                continue

            minimum_possible_sum = (
                first_value
                + sorted_numbers[first_index + 1]
                + sorted_numbers[first_index + 2]
                + sorted_numbers[first_index + 3]
            )
            if minimum_possible_sum > target_sum:
                break

            maximum_possible_sum = (
                first_value
                + sorted_numbers[total_numbers - 1]
                + sorted_numbers[total_numbers - 2]
                + sorted_numbers[total_numbers - 3]
            )
            if maximum_possible_sum < target_sum:
                continue

            self._search_second_value(
                sorted_numbers=sorted_numbers,
                first_index=first_index,
                target_sum=target_sum,
                quadruplets=quadruplets,
            )

        return quadruplets

    def _search_second_value(
        self,
        sorted_numbers: list[int],
        first_index: int,
        target_sum: int,
        quadruplets: list[list[int]],
    ) -> None:
        total_numbers = len(sorted_numbers)
        first_value = sorted_numbers[first_index]

        for second_index in range(first_index + 1, total_numbers - 2):
            second_value = sorted_numbers[second_index]

            if second_index > first_index + 1 and second_value == sorted_numbers[second_index - 1]:
                continue

            minimum_possible_sum = (
                first_value
                + second_value
                + sorted_numbers[second_index + 1]
                + sorted_numbers[second_index + 2]
            )
            if minimum_possible_sum > target_sum:
                break

            maximum_possible_sum = (
                first_value
                + second_value
                + sorted_numbers[total_numbers - 1]
                + sorted_numbers[total_numbers - 2]
            )
            if maximum_possible_sum < target_sum:
                continue

            self._collect_matching_pairs(
                sorted_numbers=sorted_numbers,
                first_index=first_index,
                second_index=second_index,
                target_sum=target_sum,
                quadruplets=quadruplets,
            )

    def _collect_matching_pairs(
        self,
        sorted_numbers: list[int],
        first_index: int,
        second_index: int,
        target_sum: int,
        quadruplets: list[list[int]],
    ) -> None:
        left_index = second_index + 1
        right_index = len(sorted_numbers) - 1
        first_value = sorted_numbers[first_index]
        second_value = sorted_numbers[second_index]

        while left_index < right_index:
            left_value = sorted_numbers[left_index]
            right_value = sorted_numbers[right_index]
            current_sum = first_value + second_value + left_value + right_value

            if current_sum == target_sum:
                quadruplets.append(
                    [first_value, second_value, left_value, right_value]
                )
                left_index += 1
                right_index -= 1

                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

            elif current_sum < target_sum:
                left_index += 1
            else:
                right_index -= 1


class Solution:
    def fourSum(self, nums: list[int], target: int) -> list[list[int]]:
        """LeetCode entry point."""
        solver = FourSumSolver()
        return solver.solve(nums, target)

Interview follow-ups

How would you generalize this to k-sum?

The usual generalization is recursive. Sort once, fix one value, then solve (k - 1)-sum on the remaining suffix. Keep doing that until the base case becomes sorted 2Sum, which is handled with two pointers. The correctness argument is the same as in 4Sum: each level commits one value, and the remaining search finds all valid completions without duplicates because the array is sorted and equal values are skipped at each level.

This works well because it turns one hard-looking problem into the same smaller problem repeatedly. The tradeoff is complexity. For k numbers, the standard recursive approach takes O(n^(k - 1)) time in the worst case, which gets expensive quickly, but it is a very natural extension in an interview.

What if the interviewer asks for the number of quadruplets instead of the actual quadruplets?

If they mean the number of distinct value quadruplets, the same sorted search still works. Instead of appending each match to a result list, increment a counter. The algorithm and duplicate-skipping rules stay essentially the same, so the correctness argument does too.

If they mean the number of index quadruplets, the problem changes. Duplicate values now matter differently because choosing different indices can count as different answers even when the value tuple looks identical. In that version, pair-sum counting techniques often become more appropriate, but they use more memory and require much more careful handling of overlap between pairs.

Can this be improved below O(n^3) time?

For the classic interview version that returns all unique quadruplets, O(n^3) with sorting and two pointers is the standard answer. There is a hash-based alternative that precomputes pair sums in roughly O(n^2) pairs and then combines compatible pairs, but that comes with O(n^2) extra space and a much messier duplicate story. It can be useful when the array is large and memory is acceptable, but it is usually not the cleanest first answer in an interview.

The important tradeoff is simplicity versus memory. The sorted O(n^3) approach is slower asymptotically, but it is easier to reason about, easy to deduplicate, and usually the expected solution unless the interviewer explicitly pushes for a pair-sum optimization.

Practical takeaway

4Sum is a good pattern-recognition problem. The main trick is not inventing a brand-new algorithm. It is recognizing that sorted 2Sum is already solved, then building 3Sum and 4Sum on top of it in a disciplined way.

Once that reduction clicks, the rest of the implementation becomes a matter of careful duplicate handling and pointer movement.