016. 3Sum Closest

Quick Identifier

Topic: two-pointers
Pattern: sort + anchor + closest two-pointer sweep
Difficulty: Medium
Companies: Google, Amazon, Meta, Apple, Bloomberg
Frequency: High
LeetCode: 16
Hint: Same as 3Sum, but update the best absolute difference instead of collecting exact matches.

Quick Sights

Time Complexity: O(n^2) - one sweep per anchor.
Space Complexity: O(1) extra excluding sorting internals.
Core Mechanism: Sort, anchor one number, sweep the suffix, and update best whenever the current sum is closer to target.

Concept Explanation

This is 3Sum with a score. Every triplet has distance abs(target - sum), and the answer is the sum with minimum distance.

Sorting lets the current sum steer pointer movement. If it is below target, moving left right can increase it. If it is above target, moving right left can decrease it. Always update the best value before moving.

Diagram

This diagram shows the pointer decisions and the step-by-step algorithm flow.

Loading diagram…

Study Pattern (SDE3+)

0-3 min: Name the pointer shape, then state the invariant and discard rule before coding.
Implementation pass: Keep pointer movement explicit; every branch must return, record an answer, or move at least one pointer.
5 min extension: Explain how the solution changes for immutable input, streaming input, many duplicate values, or many repeated queries.

Approaches

Brute force is O(n^3). Sort plus two pointers gives O(n^2) and constant extra space.

Optimal Solution

JavaScript

function threeSumClosest(nums, target) {
	nums.sort((a, b) => a - b);
	let best = nums[0] + nums[1] + nums[2];

	for (let anchor = 0; anchor < nums.length - 2; anchor++) {
		let left = anchor + 1;
		let right = nums.length - 1;
		while (left < right) {
			const sum = nums[anchor] + nums[left] + nums[right];
			if (Math.abs(target - sum) < Math.abs(target - best)) best = sum;
			if (sum === target) return target;
			if (sum < target) left++;
			else right--;
		}
	}

	return best;
}

Go

import "sort"

func threeSumClosest(nums []int, target int) int {
	sort.Ints(nums)
	best := nums[0] + nums[1] + nums[2]
	for anchor := 0; anchor < len(nums)-2; anchor++ {
		left, right := anchor+1, len(nums)-1
		for left < right {
			sum := nums[anchor] + nums[left] + nums[right]
			if abs(target-sum) < abs(target-best) {
				best = sum
			}
			if sum == target { return target }
			if sum < target { left++ } else { right-- }
		}
	}
	return best
}

func abs(x int) int {
	if x < 0 { return -x }
	return x
}