016. 3Sum Closest

At a Glance

• Topic: two-pointers
• Pattern: Two Pointers
• Difficulty: Medium
• Companies: Google, Amazon, Meta, Apple, Bloomberg
• Frequency: High
• LeetCode: 16

Problem (one-liner)

Given an integer array nums and a target, find three integers in nums whose sum is closest to target and return that sum. Exactly one answer exists per problem statement.

Recognition Cues

• "Closest sum to target" with exactly three elements
• Same sort + anchor + two pointers family as 3Sum
• Minimize absolute difference |sum - target|

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Approaches

• Brute force — O(n³) time / O(1) space — enumerate all triplets.
• Better — sort + for each anchor, two pointers adjusting toward target — O(n²) time / O(1) extra.
• Optimal — O(n²) time / O(1) extra — maintain best sum seen so far.

Optimal Solution

Go

import "sort"

func threeSumClosest(nums []int, target int) int {
	sort.Ints(nums)
	n := len(nums)
	closest := nums[0] + nums[1] + nums[2]
	for anchor := 0; anchor < n-2; anchor++ {
		left, right := anchor+1, n-1
		for left < right {
			sum := nums[anchor] + 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
}

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

JavaScript

function threeSumClosest(numbers, target) {
	numbers.sort((a, b) => a - b);
	const length = numbers.length;
	let closest = numbers[0] + numbers[1] + numbers[2];
	for (let anchor = 0; anchor < length - 2; anchor++) {
		let left = anchor + 1;
		let right = length - 1;
		while (left < right) {
			const sum = numbers[anchor] + numbers[left] + numbers[right];
			if (Math.abs(sum - target) < Math.abs(closest - target)) {
				closest = sum;
			}
			if (sum < target) {
				left++;
			} else if (sum > target) {
				right--;
			} else {
				return sum;
			}
		}
	}
	return closest;
}

Walkthrough

Input: nums = [-1,2,1,-4], target = 1 → sorted [-4,-1,1,2]

Invariant: for sorted array, moving left increases sum; moving right decreases sum — binary walk toward target.

Edge Cases

• Length exactly 3
• Duplicates
• Target equals an exact triplet sum early exit

Pitfalls

• Initializing closest incorrectly (must be a real triplet sum)
• Using floats for absolute difference with integers (stay int-safe)

Similar Problems

• 15. 3Sum — exact sum zero with dedupe.
• 18. 4Sum — four indices, sort + double pointers or nested reduction.
• 167. Two Sum II — Input Array Is Sorted — two-pointer pair toward target.

Variants

• K-sum closest — recursion + two pointers last layer.
• "Smallest distance" with duplicates allowed — tie-breaking rules.

Mind-Map Tags

#two-pointers #sort #closest-sum #absolute-diff #triplet