Generated by Codex with GPT-5

Quick facts

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

What the problem is really asking

The input is an integer array and a target value. The job is to pick exactly three numbers whose sum is as close to the target as possible.

This is different from 3Sum in one important way: there may be many triplets, but only one best answer. That changes the strategy. Instead of collecting every valid combination, the algorithm only needs to keep track of the best sum seen so far and improve it whenever a closer one appears.

Why brute force is too slow

The direct approach is to try every triplet and measure how far its sum is from the target.

That works, but it costs O(n^3) time because there are three nested choices. It is easy to reason about, but it does not scale well enough for interview expectations.

The problem becomes much easier once it is reframed as:

1. Fix one number.
2. Find the best pair among the remaining numbers.
3. Repeat for every possible first number.

Now the real question is how to search that pair efficiently.

The key insight

Sorting gives the pair search structure.

After sorting, fix one value as the first number in the triplet. Then place one pointer at the left end of the remaining suffix and one pointer at the right end.

For any current triplet sum:

• if the sum is too small, move the left pointer right to make the sum larger
• if the sum is too large, move the right pointer left to make the sum smaller

That movement is safe only because the array is sorted. Each pointer move changes the sum in a predictable direction, so the search never needs to backtrack.

How to derive the optimal solution

A clean way to derive the standard solution is:

1. Start from brute force and notice the expensive part is searching the last two numbers.
2. Sort the array so the remaining search has order.
3. Fix one value and reduce the rest to a closest 2Sum search.
4. Use two pointers because they can move toward the target in linear time.
5. Track the best sum globally and update it whenever a closer candidate appears.

That produces the standard optimal interview solution:

• Time: O(n^2)
• Extra space: O(n) in Python when using sorted(nums), or O(1) extra if sorting in place is allowed

The sort itself is O(n log n), but the repeated two-pointer scans dominate.

Practical details that make the solution better

There are two useful optimizations once the array is sorted.

First, if the smallest possible triplet for the current anchor is already greater than or equal to the target, then every later anchor will only make sums even larger. At that point the algorithm can update the answer once and stop.

Second, if the largest possible triplet for the current anchor is still less than or equal to the target, then no pair for that anchor can cross the target. The algorithm can update the answer once and skip directly to the next anchor.

These checks do not change the big-O complexity, but they remove wasted work and make the implementation feel more deliberate.

Python solution

from typing import Sequence


class ThreeSumClosestSolver:
    """Compute the triplet sum that is closest to the target."""

    def solve(self, numbers: Sequence[int], target_sum: int) -> int:
        if len(numbers) < 3:
            raise ValueError("threeSumClosest requires at least three numbers")

        sorted_numbers = sorted(numbers)
        best_sum = (
            sorted_numbers[0]
            + sorted_numbers[1]
            + sorted_numbers[2]
        )
        total_numbers = len(sorted_numbers)

        for anchor_index in range(total_numbers - 2):
            anchor_value = sorted_numbers[anchor_index]

            # Reprocessing the same anchor value cannot produce a better search space.
            if (
                anchor_index > 0
                and anchor_value == sorted_numbers[anchor_index - 1]
            ):
                continue

            smallest_possible_sum = (
                anchor_value
                + sorted_numbers[anchor_index + 1]
                + sorted_numbers[anchor_index + 2]
            )
            best_sum = self._choose_better_sum(
                candidate_sum=smallest_possible_sum,
                current_best_sum=best_sum,
                target_sum=target_sum,
            )
            if smallest_possible_sum >= target_sum:
                break

            largest_possible_sum = (
                anchor_value
                + sorted_numbers[total_numbers - 2]
                + sorted_numbers[total_numbers - 1]
            )
            best_sum = self._choose_better_sum(
                candidate_sum=largest_possible_sum,
                current_best_sum=best_sum,
                target_sum=target_sum,
            )
            if largest_possible_sum <= target_sum:
                continue

            best_sum = self._scan_pairs_for_anchor(
                sorted_numbers=sorted_numbers,
                anchor_index=anchor_index,
                target_sum=target_sum,
                current_best_sum=best_sum,
            )

            if best_sum == target_sum:
                return best_sum

        return best_sum

    def _scan_pairs_for_anchor(
        self,
        sorted_numbers: list[int],
        anchor_index: int,
        target_sum: int,
        current_best_sum: int,
    ) -> int:
        left_index = anchor_index + 1
        right_index = len(sorted_numbers) - 1
        anchor_value = sorted_numbers[anchor_index]
        best_sum = current_best_sum

        while left_index < right_index:
            current_sum = (
                anchor_value
                + sorted_numbers[left_index]
                + sorted_numbers[right_index]
            )
            best_sum = self._choose_better_sum(
                candidate_sum=current_sum,
                current_best_sum=best_sum,
                target_sum=target_sum,
            )

            if current_sum == target_sum:
                return current_sum

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

        return best_sum

    @staticmethod
    def _choose_better_sum(
        candidate_sum: int,
        current_best_sum: int,
        target_sum: int,
    ) -> int:
        candidate_distance = abs(candidate_sum - target_sum)
        best_distance = abs(current_best_sum - target_sum)

        if candidate_distance < best_distance:
            return candidate_sum

        if candidate_distance > best_distance:
            return current_best_sum

        # The problem guarantees a unique best answer, but keeping a
        # deterministic tie-breaker makes the helper well-defined.
        return min(candidate_sum, current_best_sum)


class Solution:
    def threeSumClosest(self, nums: list[int], target: int) -> int:
        solver = ThreeSumClosestSolver()
        return solver.solve(numbers=nums, target_sum=target)

Why this works

For each fixed first number, the remaining pair search is performed on a sorted suffix.

If the current sum is below the target, moving the left pointer right is the only move that can increase the sum. If the current sum is above the target, moving the right pointer left is the only move that can decrease it. So every pointer move is logically justified by the ordering of the array.

Because every anchor runs a complete two-pointer scan over its suffix, the algorithm checks every relevant triplet pattern without falling back to cubic brute force. Keeping the best sum seen so far guarantees that the final answer is the closest triplet sum overall.

Interview follow-ups

What if the interviewer wants the actual triplet, not just the sum?

The same sorted two-pointer strategy still works. Instead of storing only best_sum, store both best_sum and best_triplet. Every time a closer sum appears, replace both pieces of state. The correctness argument is unchanged because the search order is unchanged; the algorithm is still exploring the same candidate triplets. The complexity stays O(n^2) time, with only O(1) extra bookkeeping beyond the sorted array.

Why is moving the pointers greedily safe?

This is a common follow-up because it tests whether the candidate understands the role of sorting. Suppose the current sum is too small. Moving the right pointer left would only make the sum even smaller, so it cannot be the right move if the goal is to get closer to a larger target. The only promising move is to increase the left pointer. The symmetric argument holds when the current sum is too large. That monotonic structure is exactly why sorting is worth paying for up front. Without sorting, there is no equally clean O(n^2) pointer rule.

How would you generalize this to k-Sum Closest?

The usual extension is recursive. Sort the array, fix one number, and solve (k - 1)-Sum Closest on the suffix with an adjusted target. The base case is 2Sum Closest, which uses the same two-pointer scan as this problem. This works because each recursive level reduces the problem by one choice while preserving the sorted structure. The tradeoff is complexity: 3Sum Closest is O(n^2), 4Sum Closest becomes O(n^3), and in general the pattern grows to roughly O(n^(k-1)), so it is practical only for small fixed k.

Practical takeaway

The core trick is to stop thinking about three free choices and start thinking about one fixed choice plus a closest-pair search.

Once the array is sorted, the problem becomes a direct application of two pointers and “best so far” tracking. That reframing is what turns an obvious O(n^3) solution into the standard O(n^2) interview answer.