16 - 3Sum Closest

Difficulty: Medium | Pattern: Two Pointers / Sorting | Company tags: Amazon, Facebook, Google

Problem Statement

Given an integer array nums of length n and an integer target, find three integers 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 closest to 1 is (-1 + 2 + 1) = 2.

Example 2:

Input: nums = [0,0,0], target = 1
Output: 0

Approach: Sort + Two Pointers — O(n²)

Key insight: Same as 3Sum. Sort the array. For each element nums[i], use two pointers on the remaining subarray to find the pair that makes the total closest to target. Move the pointer that would bring the sum closer.

def threeSumClosest(nums: list[int], target: int) -> int:
    nums.sort()
    closest = float('inf')
    
    for i in range(len(nums) - 2):
        left, right = i + 1, len(nums) - 1
        
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            
            if abs(total - target) < abs(closest - target):
                closest = total
            
            if total < target:
                left += 1
            elif total > target:
                right -= 1
            else:
                return total  # exact match
    
    return closest

Algorithm Flow

Dry Run

nums = [-1, 2, 1, -4], target = 1

After sorting: [-4, -1, 1, 2]

i	left	right	total	diff from target	closest
0 (-4)	1 (-1)	3 (2)	-3	4	-3
0 (-4)	2 (1)	3 (2)	-1	2	-1
0 (-4)	3	3	left=right, stop
1 (-1)	2 (1)	3 (2)	2	1	2
1 (-1)	3	3	left=right, stop

Return 2 ✓

Why Sorting + Two Pointers Works

After sorting:

• If total < target: increase the sum by moving left right (larger values)
• If total > target: decrease the sum by moving right left (smaller values)
• This guarantees we explore all promising combinations without O(n³) brute force

Edge Cases

• Exactly 3 elements → only one triple to check
• Exact match found → early return
• All same values → result is always that value × 3

Complexity

• Time: O(n²) — O(n log n) sort + O(n²) two-pointer passes
• Space: O(1) — sorting in-place (or O(log n) for sort stack)

Compare with 3Sum (LC 15): 3Sum finds all triples summing to 0; 3Sum Closest finds the single triple closest to a target. Same algorithmic pattern, different stopping condition.

Key Terms

Term	Definition
Two pointers	left/right indices converging on a sorted array to explore sum combinations in linear time per fixed element.
Sorting preprocessing	Ordering the array first so pointer movement has a predictable effect (moving left right increases the sum, right left decreases it).
Fixed element + inner scan	Iterating i over each index while running a two-pointer scan on the remainder — reduces 3Sum from O(n³) to O(n²).
Closest-to-target tracking	Maintaining a running best answer by comparing abs(total - target) instead of requiring an exact match.

FAQ

Q: Can this be solved without extra space? A: Yes — sorting can be done in place (O(1) auxiliary beyond the sort's own O(log n) stack), and the two-pointer scan needs no additional data structures.

Q: What if the input array has fewer than 3 elements? A: The problem guarantees n >= 3, but defensively you'd return early or raise an error, since no triple can be formed with fewer than 3 elements.

Q: What if multiple triples are equally close to the target? A: The problem guarantees a unique closest sum, so ties aren't a concern here; if they were, the first one found during the scan would be returned since < (not <=) is used in the update check.

Q: How would this change if we needed the actual triple (indices/values) instead of just the sum? A: Track nums[i], nums[left], nums[right] alongside closest whenever it updates, storing the triple itself rather than just the sum.

Q: How does this differ from the original 3Sum (LC 15) problem? A: 3Sum finds all unique triples summing exactly to a target (needs duplicate-skipping logic and returns a list); 3Sum Closest finds a single triple whose sum is nearest to the target and returns just that sum — same scaffold, different goal and stopping condition.

Quick Revision

• Problem: find the triple sum closest to target; return the sum, not the triple.
• Pattern: sort array, fix one element, two-pointer scan the rest — classic 3Sum scaffold.
• Move left right if total < target (need a bigger sum), move right left if total > target.
• Track closest via min comparison on abs(total - target).
• Early return on exact match (total == target).
• Time: O(n²) after O(n log n) sort; Space: O(1) extra (ignoring sort stack).
• Edge case: exactly 3 elements → single triple, trivial closest.
• Edge case: all identical values → closest sum is that value times 3.
• Contrast with 3Sum (LC 15): same setup, different objective (all exact-sum triples vs. one closest triple).

Related Problems

• 15 - 3Sum — the base problem this one's approach is directly adapted from.
• 18 - 4Sum — extends the fixed-element-plus-two-pointer pattern to four numbers.
• 259 - 3Sum Smaller — same two-pointer scaffold, counts triples under a threshold instead of finding the closest sum.