--- title: 3Sum Closest description: Find three integers in an array that sum closest to the target value. date: 2024-03-14 tag: ["Medium", "Array", "Two Pointers"] author: Easy Algo premium: false percentage: 30 --- ## Problem > LeetCode link: [3Sum Closest](https://leetcode.com/problems/3sum-closest/) 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 that is closest to the target is 2. (-1 + 2 + 1 = 2). ``` **Example 2:** ``` Input: nums = [0,0,0], target = 1 Output: 0 ``` **Constraints:** ``` 3 <= nums.length <= 1000 -1000 <= nums[i] <= 1000 -10^4 <= target <= 10^4 ``` ## Solution **Problem Simplified:** Given a set of numbers and a target value, find three numbers whose sum is as close as possible to the target. The challenge is to minimize the absolute difference between the sum and the target value. **Edge Cases and Test Examples:** * **Edge Cases:** * Minimum array length (3): `nums = [1, 2, 3], target = 5` * Duplicate numbers: `nums = [0, 0, 0], target = 1` * Extreme target values: `nums = [-1, 0, 1], target = 10000` or `target = -10000` * **Test Cases:** * `nums = [-1, 2, 1, -4], target = 1, Output: 2` * `nums = [0, 0, 0], target = 1, Output: 0` * `nums = [-1, 2, 1, -4], target = -1, Output: -1` * `nums = [1, 1, 1, 0], target = -100, Output: 2` * `nums = [1, 1, -1, -1, 3], target = -1, Output: -1` **Solution Analysis:** | Approach | Advantages | Disadvantages | Time Complexity | Space Complexity | | -------- | ---------- | ------------- | -------------- | ---------------- | | Brute Force | Simple to understand | Inefficient for large inputs | O(n³) | O(1) | | Sort + Two Pointers | Efficient, avoids unnecessary calculations | Modifies input array (requires copy if modification not allowed) | O(n log n) | O(1) | * **Complexity Analysis:** * **Time Complexity:** Brute force requires three nested loops (O(n³)), while Sort + Two Pointers needs sorting (O(n log n)) plus linear traversal. * **Space Complexity:** Both approaches use only a few variables, resulting in O(1) space usage. **Recommended Approach:** Sort + Two Pointers offers the best balance of efficiency and implementation simplicity. **Python Implementation:** **Version 1: With Detailed Comments** ```python class Solution: def threeSumClosest(self, nums: list[int], target: int) -> int: """ Find three integers in the array with sum closest to target. Args: nums (List[int]): Array of integers target (int): Target value Returns: int: Sum of three integers closest to target """ # 1. Sort array for two-pointer approach nums.sort() n = len(nums) # 2. Initialize closest sum with infinity closest_sum = float('inf') # 3. Iterate through array, fixing first number for i in range(n - 2): # 4. Use two pointers for remaining numbers left = i + 1 # Left pointer for second number right = n - 1 # Right pointer for third number while left < right: current_sum = nums[i] + nums[left] + nums[right] # Calculate current sum # 5. If exact match found, return immediately if current_sum == target: return target # 6. Update closest sum if current sum is closer if abs(current_sum - target) < abs(closest_sum - target): closest_sum = current_sum # 7. Move pointers based on comparison with target if current_sum < target: left += 1 # Increase sum by moving left pointer right else: right -= 1 # Decrease sum by moving right pointer left # 8. Return the closest sum found return closest_sum ``` **Version 2: Clean Implementation** ```python class Solution: def threeSumClosest(self, nums: list[int], target: int) -> int: nums.sort() n = len(nums) closest_sum = float('inf') for i in range(n - 2): left = i + 1 right = n - 1 while left < right: current_sum = nums[i] + nums[left] + nums[right] if current_sum == target: return target if abs(current_sum - target) < abs(closest_sum - target): closest_sum = current_sum if current_sum < target: left += 1 else: right -= 1 return closest_sum ``` **Step-by-Step Execution:** 1. **Sorting:** First, sort the input array `nums` to enable the two-pointer approach. 2. **Initialization:** Set `closest_sum` to infinity as the initial value. 3. **Main Loop:** * For each element `nums[i]`, use two pointers to find complementary numbers. * `left` pointer starts at `i + 1`. * `right` pointer starts at array end. 4. **Two-Pointer Process:** * Calculate `current_sum = nums[i] + nums[left] + nums[right]`. * If `current_sum` equals `target`, we've found the exact solution. * Update `closest_sum` if `current_sum` is closer to `target`. * Move pointers based on comparison with target: * If sum is too small, increment `left`. * If sum is too large, decrement `right`. 5. **Result:** Return the sum that's closest to the target value.