DSA SheetMedium
EditorialPractice

2 POINTERS › TWO POINTER ON ARRAYS

3Sum Closest

MediumEditorial · 7 minGenerated by gpt-5.6-luna · Aug 26

Open — the attempt gate is not wired up yet

This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.

Try it yourself first →

Intuitionwhy sorting makes the search move in one direction

Choose the first number at index i, then the other two numbers must come from the suffix after i. Once that suffix is sorted, the smallest possible pair is at the left end and the largest possible pair is at the right end. Their sum tells you which extreme can still move toward the target without skipping a better candidate.

If the three-number sum is too small, moving the right pointer left would make it even smaller, so that move cannot help. Move left inward instead. If the sum is too large, move right inward. Every visited sum is compared with the best one so far, and an exact target ends the search because no sum can be closer than zero difference.

A sorted array with one fixed index and two pointers closing inwardA row of sorted array values runs from left to right, with index i marked on one fixed value. The left pointer starts at the first value after i, and the right pointer starts at the last value. A bracket or label identifies the three values currently being added. Because the current sum is below the target, the left pointer has an arrow moving right while the right pointer is held still, showing that increasing the smaller pair member is the only useful move.1357912151801234567fixed ileft pointersum too small: move left →right pointersum too large: move right ←With i fixed, a sum below target can only rise by moving left rightward.

Approachone fixed value, one monotonic pair search

  1. Sort nums so that changing either pointer has a predictable effect on the three-number sum; without ordering, neither pointer movement would safely rule out candidates.
  2. Initialize closest with the sum of the first three sorted values, rather than with zero or an arbitrary sentinel, so every later comparison is against a real valid triple.
  3. For each index i from 0 through n - 3, fix nums[i] and set left to i + 1 and right to n - 1; these bounds guarantee three distinct indices while searching the remaining suffix.
  4. Compute nums[i] + nums[left] + nums[right] and update closest when its distance from target is smaller; otherwise a nearer triple can be visited and then discarded.
  5. If the sum is smaller than target, increment left because the sorted order makes every move of right either smaller or no better; if the sum is larger, decrement right for the symmetric reason.
  6. If the sum equals target, return immediately because its distance from target is zero and the promised unique answer cannot be improved.
  7. Continue while left < right, then advance i after that pair search is exhausted; every fixed index gets its own complete range without reusing an index.

Complexityquadratic scanning after one sort

MEASUREBOUNDWHY
TimeO(n^2)Sorting costs O(n log n). For each of the O(n) choices of i, left only moves right and right only moves left, so that inner scan performs O(n) total pointer moves rather than restarting work at every pair.
SpaceO(log n) extra, worst caseThe two pointers and scalar variables use O(1) space. The implementation's in-place sort may use O(log n) stack space in the worst case, so that dominates the extra bound; the returned integer requires no output storage beyond the result value.
Here n is the length of nums. The returned sum is output and is excluded from extra space.

Annotated solutionC++ · sorted array with a fixed index and two pointers

CPPSort the values, scan every fixed index, and keep the closest triple sum.
#include <algorithm>
#include <cstdlib>
#include <vector>

using namespace std;

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int closest = nums[0] + nums[1] + nums[2];

        for (int i = 0; i < n - 2; ++i) {
            int left = i + 1;
            int right = n - 1;

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

                if (abs(sum - target) < abs(closest - target)) {
                    closest = sum;
                }

                if (sum < target) {
                    ++left;
                } else if (sum > target) {
                    --right;
                } else {
                    return sum;
                }
            }
        }

        return closest;
    }
};

The initialization of closest is deliberately tied to nums[0], nums[1], and nums[2]. Those are valid distinct indices, so the first comparison has a meaningful baseline even when every possible sum is negative or every possible sum is positive. The update uses strict inequality because an exact tie does not need to replace an already valid answer.

Common mistakestwo wrong shapes that look plausible

Previous · 3Sum