Domain 2MediumCORE

3Sum Closest

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.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Array#Two Pointers

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 nn 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 n=3n=3, 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 target allows us to stop early as the difference cannot be smaller than 0.

Intuition

First thought: Brute force using three nested loops (O(n3)O(n^3)). For n=1000n=1000, this is roughly a billion operations, which will time out on standard platforms (usually allowing ∼108\sim 10^8 ops/sec). We need something faster than cubic.

Second thought: Can we optimize the search space? If we sort the array first (O(nlog⁡n)O(n \log n)), 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 O(n3)O(n^3) to O(n2)O(n^2).

Approach

  1. Sort nums in ascending order. This enables two-pointer logic and handles negative values naturally.
  2. 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 against target to update closest_sum.
  3. Iterate through the array with index i from 00 to n−3n-3. This element acts as our first number in the triplet.
  4. For each nums[i], set two pointers: left = i + 1 and right = n - 1.
  5. While left < right:
    • Calculate current_sum = nums[i] + nums[left] + nums[right].
    • Check if the absolute difference between current_sum and target is less than that of our current best (closest_sum). If so, update closest_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: increment left to increase sum.
      • Else (current_sum > target): decrement right to decrease sum.
  6. After the loops finish, return closest_sum.

Complexity Analysis

  • Time: O(n2)O(n^2). Sorting takes O(nlog⁡n)O(n \log n), but is dominated by the nested loop structure which runs in O(n2)O(n^2) (outer loop nn, inner two-pointer scan ≈1\approx 1 pass). With N=1000N=1000, operations are roughly 5×1065 \times 10^6, well within limits.
  • Space: O(1)O(1). 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 (O(n)O(n)).

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 (n=3n=3): The loop runs once, left and right are adjacent. Logic holds without index out of bounds errors because range is set to n−2n-2.
  • 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 == target check 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.