A complete visual walkthrough of the sort + two pointer approach — tracking the closest sum to a target instead of an exact match.
Given an integer array nums of length n and an integer target, find three integers at distinct indices in nums such that the sum is closest to target.
Return the sum of the three integers.
You may assume that each input would have exactly one solution.
Example 1:
Input: nums = [-1,2,1,-4], target = 1 Output: 2 Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
Example 2:
Input: nums = [0,0,0], target = 1 Output: 0 Explanation: The sum that is closest to the target is 0. (0 + 0 + 0 = 0).
Constraints:
3 <= nums.length <= 500-1000 <= nums[i] <= 1000-104 <= target <= 104The most straightforward approach: try every combination of three elements, compute the sum, and keep track of whichever sum is closest to the target.
int closest = nums[0] + nums[1] + nums[2]; for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) for (int k = j + 1; k < n; k++) { int sum = nums[i] + nums[j] + nums[k]; if (Math.abs(sum - target) < Math.abs(closest - target)) closest = sum; }
closest := nums[0] + nums[1] + nums[2] for i := 0; i < n; i++ { for j := i + 1; j < n; j++ { for k := j + 1; k < n; k++ { sum := nums[i] + nums[j] + nums[k] if abs(sum-target) < abs(closest-target) { closest = sum } } } }
closest = nums[0] + nums[1] + nums[2] for i in range(n): for j in range(i + 1, n): for k in range(j + 1, n): total = nums[i] + nums[j] + nums[k] if abs(total - target) < abs(closest - target): closest = total
let mut closest = nums[0] + nums[1] + nums[2]; for i in 0..n { for j in (i + 1)..n { for k in (j + 1)..n { let sum = nums[i] + nums[j] + nums[k]; if (sum - target).abs() < (closest - target).abs() { closest = sum; } } } }
let closest = nums[0] + nums[1] + nums[2]; for (let i = 0; i < n; i++) for (let j = i + 1; j < n; j++) for (let k = j + 1; k < n; k++) { const sum = nums[i] + nums[j] + nums[k]; if (Math.abs(sum - target) < Math.abs(closest - target)) closest = sum; }
For n = 1000, this checks roughly ~167 million triplets. It works, but is far too slow for LeetCode constraints.
Can we do better? Yes. This problem is a variant of 3Sum. Instead of finding sums equal to zero, we track the sum closest to a target. The same sort + two pointer technique applies, reducing us from O(n³) to O(n²).
Sort the array first. Then for each fixed element nums[i], use two pointers to scan the remaining elements. Instead of checking sum == 0, compare |sum - target| against the current best and keep the closer one.
closest = nums[0] + nums[1] + nums[2] as a starting reference.i iterates from 0. left starts at i+1, right at the end.|sum - target| is smaller than the current best, update closest. If sum < target, move left up. If sum > target, move right down. If sum == target, return immediately.Why does sorting make this work? In a sorted array, the sum of a triplet is monotonically affected by pointer movement. Moving the left pointer right increases the sum; moving the right pointer left decreases it. This means we can always steer toward the target without backtracking.
Let's trace through the example nums = [-1, 2, 1, -4], target = 1. After sorting:
Initial closest = nums[0] + nums[1] + nums[2] = -4 + (-1) + 1 = -4. Difference from target: |(-4) - 1| = 5.
Notice the progression: closest went from -4 (diff 5) to -3 (diff 4) to -1 (diff 2) to 2 (diff 1). Each time we found a better sum, we updated. The two-pointer technique systematically narrows in on the target from both sides.
Make sure your solution handles these correctly:
No duplicate handling needed! Unlike 3Sum, we do not need to skip duplicates because we are returning a single integer (the closest sum), not a list of unique triplets. Duplicates in the array won't produce wrong answers — at worst they cause redundant comparisons.
class Solution { public int threeSumClosest(int[] nums, int target) { // Step 1: Sort — enables two-pointer technique Arrays.sort(nums); // Initialize with the first triplet's sum int closest = nums[0] + nums[1] + nums[2]; for (int i = 0; i < nums.length - 2; i++) { int left = i + 1, right = nums.length - 1; while (left < right) { int sum = nums[i] + nums[left] + nums[right]; // Update closest if this sum is nearer to target if (Math.abs(sum - target) < Math.abs(closest - target)) { closest = sum; } if (sum < target) { left++; // Need a larger sum → move left right } else if (sum > target) { right--; // Need a smaller sum → move right left } else { return sum; // Exact match — can't do better } } } return closest; } }
func threeSumClosest(nums []int, target int) int { // Step 1: Sort — enables two-pointer technique sort.Ints(nums) // Initialize with the first triplet's sum closest := nums[0] + nums[1] + nums[2] abs := func(x int) int { if x < 0 { return -x } return x } for i := 0; i < len(nums)-2; i++ { left, right := i+1, len(nums)-1 for left < right { sum := nums[i] + nums[left] + nums[right] // Update closest if this sum is nearer to target if abs(sum-target) < abs(closest-target) { closest = sum } if sum < target { left++ // Need a larger sum → move left right } else if sum > target { right-- // Need a smaller sum → move right left } else { return sum // Exact match — can't do better } } } return closest }
def three_sum_closest(nums: list[int], target: int) -> int: # Step 1: Sort — enables two-pointer technique nums.sort() # Initialize with the first triplet's sum closest = nums[0] + nums[1] + nums[2] for i in range(len(nums) - 2): left, right = i + 1, len(nums) - 1 while left < right: total = nums[i] + nums[left] + nums[right] # Update closest if this sum is nearer to target if abs(total - target) < abs(closest - target): closest = total if total < target: left += 1 # Need a larger sum → move left right elif total > target: right -= 1 # Need a smaller sum → move right left else: return total # Exact match — can't do better return closest
impl Solution { pub fn three_sum_closest(nums: Vec<i32>, target: i32) -> i32 { // Step 1: Sort — enables two-pointer technique let mut nums = nums; nums.sort(); // Initialize with the first triplet's sum let mut closest = nums[0] + nums[1] + nums[2]; let n = nums.len(); for i in 0..n.saturating_sub(2) { let (mut left, mut right) = (i + 1, n - 1); while left < right { let sum = nums[i] + nums[left] + nums[right]; // Update closest if this sum is nearer to target if (sum - target).abs() < (closest - target).abs() { closest = sum; } if sum < target { left += 1; // Need a larger sum → move left right } else if sum > target { right -= 1; // Need a smaller sum → move right left } else { return sum; // Exact match — can't do better } } } closest } }
function threeSumClosest(nums: number[], target: number): number { // Step 1: Sort — enables two-pointer technique nums.sort((a, b) => a - b); // Initialize with the first triplet's sum let closest = nums[0] + nums[1] + nums[2]; for (let i = 0; i < nums.length - 2; i++) { let left = i + 1, right = nums.length - 1; while (left < right) { const sum = nums[i] + nums[left] + nums[right]; // Update closest if this sum is nearer to target if (Math.abs(sum - target) < Math.abs(closest - target)) { closest = sum; } if (sum < target) { left++; // Need a larger sum → move left right } else if (sum > target) { right--; // Need a smaller sum → move right left } else { return sum; // Exact match — can't do better } } } return closest; }
Enter an array and a target, then step through the algorithm to see how the two pointers converge on the closest sum.
Sorting costs O(n log n), then the outer loop runs O(n) times with an inner two-pointer scan of O(n) each, giving O(n2) total. Space is O(1) — we only use a few integer variables and the sort is in-place.
Three nested loops enumerate every triplet (i, j, k), computing the sum and comparing its distance to the target. This examines n*(n-1)*(n-2)/6 combinations, giving O(n3). Only a single variable tracks the closest sum, so space is O(1).
After an O(n log n) sort, the outer loop fixes one element in O(n). For each fixed element, two pointers converge from both ends in O(n), steering toward the target based on whether the current sum is too low or too high. Total: O(n2). Only pointer variables are used, so space stays O(1).
Identical complexity to 3Sum. Tracking the "closest" sum instead of an "exact" match does not change the time or space. The two-pointer movement logic is the same — sum < target moves left up, sum > target moves right down — we simply compare distances instead of checking equality.
Review these before coding to avoid predictable interview regressions.
Wrong move: Advancing both pointers shrinks the search space too aggressively and skips candidates.
Usually fails on: A valid pair can be skipped when only one side should move.
Fix: Move exactly one pointer per decision branch based on invariant.