16. 3Sum Closest
Model: qwen3.5:9b
Topics: Array,Two Pointers
FAANG asked: 1
Acceptance rate: 46.3%
Problem Breakdown
We are given an array nums and a target integer. Our goal is to select exactly three distinct elements from nums such that their sum has the minimum absolute difference with respect to target. We need to return this specific sum value, not the indices or the triplet itself.
Key constraints: The input size can be up to 1000. Values are within standard integer ranges (no overflow concerns in Python). There is exactly one solution guaranteed per problem statement, though practically we just want the closest sum found during our search.
Implicit considerations:
- Negative numbers: Sorting handles negatives correctly for the two-pointer logic; they don’t break arithmetic comparisons here.
- Small arrays: If , there is only one possible triplet (all elements). The algorithm must handle this without crashing or skipping iterations incorrectly.
- Perfect match: While not strictly required to return immediately, finding an exact sum equal to
targetallows us to stop early as the difference cannot be smaller than 0.
Intuition
First thought: Brute force using three nested loops (). For , this is roughly a billion operations, which will time out on standard platforms (usually allowing ops/sec). We need something faster than cubic.
Second thought: Can we optimize the search space? If we sort the array first (), for any fixed element nums[i], the remaining two elements can be found using a Two Pointers approach on the sorted subarray [i+1, end].
Why does sorting help? Because it creates monotonicity. For a specific left pointer and right pointer:
- If
current_sum < target: We need a larger sum to get closer (or equal). Since the array is sorted, moving the left pointer forward increases the sum. - If
current_sum > target: We need a smaller sum. Moving the right pointer backward decreases the sum.
This allows us to discard entire ranges of combinations that are guaranteed not to be better than what we’ve already seen or found, reducing complexity from to .
Approach
- Sort
numsin ascending order. This enables two-pointer logic and handles negative values naturally. - Initialize a variable
closest_sum. A safe initialization is the sum of the first three elements (nums[0] + nums[1] + nums[2]). We also track the minimum difference found so far, or simply compare absolute differences directly againsttargetto updateclosest_sum. - Iterate through the array with index
ifrom to . This element acts as our first number in the triplet. - For each
nums[i], set two pointers:left = i + 1andright = n - 1. - While
left < right:- Calculate
current_sum = nums[i] + nums[left] + nums[right]. - Check if the absolute difference between
current_sumandtargetis less than that of our current best (closest_sum). If so, updateclosest_sum. - Optimization: If
current_sum == target, we found a perfect match. Return immediately since 0 distance cannot be improved upon. - Adjust pointers:
- If
current_sum < target: incrementleftto increase sum. - Else (
current_sum > target): decrementrightto decrease sum.
- If
- Calculate
- After the loops finish, return
closest_sum.
Complexity Analysis
- Time: . Sorting takes , but is dominated by the nested loop structure which runs in (outer loop , inner two-pointer scan pass). With , operations are roughly , well within limits.
- Space: . We only use a few variables for pointers and sums, assuming the sort is done in-place or we ignore Python’s Timsort stack overhead ().
Solution
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
# Sort to enable two-pointer technique and handle negatives correctly
nums.sort()
n = len(nums)
closest_sum = 0
# Initialize with the sum of first three elements.
# This is safe because constraints guarantee length >= 3.
closest_sum = nums[0] + nums[1] + nums[2]
for i in range(n - 2):
left, right = i + 1, n - 1
while left < right:
current_sum = nums[i] + nums[left] + nums[right]
# Check if this sum is closer to target than our best so far
diff_current = abs(current_sum - target)
diff_best = abs(closest_sum - target)
if diff_current < diff_best:
closest_sum = current_sum
# Optimization: Exact match found, cannot do better
if current_sum == target:
return current_sum
# Move pointers based on comparison with target
if current_sum < target:
left += 1
else:
right -= 1
return closest_sum
Edge Cases Handled
- Minimum Array Size (): The loop runs once,
leftandrightare adjacent. Logic holds without index out of bounds errors because range is set to . - Negative Numbers: Sorting places negatives at the start; two-pointer logic works identically regardless of sign (e.g.,
-10 + 5 < -5). - Perfect Match: The
if current_sum == targetcheck ensures we return immediately, optimizing performance for cases where an exact solution exists. - No Exact Solution: The initialization with the first triplet and subsequent updates ensure a valid sum is always returned even if no combination equals
target.