3Sum Closest

LeetCode 16: 3Sum Closest Solution & Explanation

Problem Overview

TL;DR: Sort the input array and iterate through it, using the Two Pointers technique to find the pair of numbers that, combined with the current number, produces a sum closest to the target.

The 3Sum Closest problem requires finding three integers within an array nums such that their sum is closest to a specific target value. Unlike the standard 3Sum problem which seeks a sum of exactly zero, this variation asks for the minimum absolute difference between the triplet sum and the target. The output must be the actual sum of these three integers.

This is a popular interview question that tests the ability to optimize a combinatorial problem using sorting and pointers. The LeetCode 16 solution relies on reducing the search space from cubic time to quadratic time.

Brute Force Approach for 3Sum Closest

The naive approach is to evaluate every possible combination of three numbers in the array. We iterate through the array with three nested loops to select the first, second, and third numbers, calculate their sum, and compare the absolute difference with the target against the current best difference.

Pseudo-code:

Initialize closestSum = infinity
For i from 0 to n-3:
    For j from i+1 to n-2:
        For k from j+1 to n-1:
            currentSum = nums[i] + nums[j] + nums[k]
            If abs(target - currentSum) < abs(target - closestSum):
                closestSum = currentSum
Return closestSum

Complexity Analysis: The time complexity is $O(n^3)$ because of the three nested loops. With the constraint $n \le 500$, the number of operations is approximately $1.25 \times 10^8$. While this might technically pass within a generous time limit, it is highly inefficient compared to the optimal solution. In an interview context, an $O(n^3)$ solution is generally considered a failure to identify the optimization pattern.

Algorithm Strategy: Two Pointer Patterns

1. Sort the Array: First, sort nums in ascending order. This is a prerequisite for the converging pointers strategy.
2. Initialize Result: Store the sum of the first three elements as the initial closestSum.
3. Iterate with Pivot: Loop through the array with index i from 0 to n-2. This i represents the first element of the triplet.
4. Two Pointers Initialization: For each i, set left to i + 1 and right to n - 1.
5. Converge Pointers: While left < right:
   • Calculate currentSum = nums[i] + nums[left] + nums[right].
   • Check if abs(target - currentSum) is smaller than abs(target - closestSum). If so, update closestSum.
   • Directional Logic:
     • If currentSum < target, increment left to increase the sum.
     • If currentSum > target, decrement right to decrease the sum.
     • If currentSum == target, return target immediately (absolute difference is 0).
6. Return: After all loops complete, return closestSum.

Execution Flow

Let's trace the algorithm with nums = [-1, 2, 1, -4] and target = 1.

1. Sort: The array becomes [-4, -1, 1, 2].
2. Init: closestSum is initialized (e.g., sum of first three: -4 + -1 + 1 = -4).
3. Outer Loop (i = 0): nums[i] = -4.
   • left points to index 1 (val = -1), right points to index 3 (val = 2).
   • currentSum = -4 + (-1) + 2 = -3.
   • Distance to target: abs(1 - (-3)) = 4. Previous best was abs(1 - (-4)) = 5.
   • Update closestSum to -3.
   • Since -3 < 1 (target), move left forward.
   • New left is index 2 (val = 1). right is index 3 (val = 2).
   • currentSum = -4 + 1 + 2 = -1.
   • Distance: abs(1 - (-1)) = 2. Update closestSum to -1.
   • Since -1 < 1, move left forward.
   • left meets right. Loop ends.
4. Outer Loop (i = 1): nums[i] = -1.
   • left points to index 2 (val = 1), right points to index 3 (val = 2).
   • currentSum = -1 + 1 + 2 = 2.
   • Distance: abs(1 - 2) = 1. Previous best was 2 (from sum -1).
   • Update closestSum to 2.
   • Since 2 > 1, move right backward.
   • left meets right. Loop ends.
5. Termination: Outer loop finishes. Return closestSum which is 2.

Proof of Correctness

The correctness relies on the sorted property of the array. For any fixed element nums[i], we are searching for a pair (nums[left], nums[right]) such that their sum is optimal.

Suppose currentSum < target. Any pair involving nums[left] and an index smaller than right will have a sum smaller than currentSum (because the array is sorted). Since currentSum is already smaller than target, making it smaller increases the error. Therefore, we can safely discard the current left combined with any index to the left of right. We must move left forward to potentially find a better sum. The symmetric logic applies when currentSum > target. This greedy elimination ensures we find the optimal pair for each i without checking all $O(n^2)$ pairs, reducing the inner search to $O(n)$.

Pattern Reuse Notes

The "Two Pointers - Converging" pattern used in LeetCode 16 is a fundamental technique for array problems involving sums or areas.

• LeetCode 15: 3Sum: Identical structure, but checks for sum == 0 and requires handling duplicates strictly.
• LeetCode 18: 4Sum: Extends the pattern by adding an extra loop, reducing $O(n^4)$ to $O(n^3)$.
• LeetCode 167: Two Sum II - Input Array Is Sorted: The base case for this pattern ($O(n)$).
• LeetCode 11: Container With Most Water: Uses converging pointers to optimize area calculation, moving the pointer that limits the height.

Reference Implementation

C++ Solution for LeetCode 16

1class Solution {
2public:
3    int threeSumClosest(vector<int>& nums, int target) {
4        sort(nums.begin(), nums.end());
5        int closestSum = nums[0] + nums[1] + nums[2];
6        int n = nums.size();
7
8        for (int i = 0; i < n - 2; ++i) {
9            int left = i + 1;
10            int right = n - 1;
11
12            while (left < right) {
13                int currentSum = nums[i] + nums[left] + nums[right];
14
15                if (abs(target - currentSum) < abs(target - closestSum)) {
16                    closestSum = currentSum;
17                }
18
19                if (currentSum < target) {
20                    left++;
21                } else if (currentSum > target) {
22                    right--;
23                } else {
24                    // Difference is 0, cannot get closer
25                    return currentSum;
26                }
27            }
28        }
29        return closestSum;
30    }
31};

Java Solution for LeetCode 16

1class Solution {
2    public int threeSumClosest(int[] nums, int target) {
3        Arrays.sort(nums);
4        int closestSum = nums[0] + nums[1] + nums[2];
5        int n = nums.length;
6
7        for (int i = 0; i < n - 2; i++) {
8            int left = i + 1;
9            int right = n - 1;
10
11            while (left < right) {
12                int currentSum = nums[i] + nums[left] + nums[right];
13
14                if (Math.abs(target - currentSum) < Math.abs(target - closestSum)) {
15                    closestSum = currentSum;
16                }
17
18                if (currentSum < target) {
19                    left++;
20                } else if (currentSum > target) {
21                    right--;
22                } else {
23                    // Exact match found
24                    return currentSum;
25                }
26            }
27        }
28        return closestSum;
29    }
30}

Python Solution for LeetCode 16

1class Solution:
2    def threeSumClosest(self, nums: List[int], target: int) -> int:
3        nums.sort()
4        n = len(nums)
5        closest_sum = nums[0] + nums[1] + nums[2]
6
7        for i in range(n - 2):
8            left = i + 1
9            right = n - 1
10
11            while left < right:
12                current_sum = nums[i] + nums[left] + nums[right]
13
14                if abs(target - current_sum) < abs(target - closest_sum):
15                    closest_sum = current_sum
16
17                if current_sum < target:
18                    left += 1
19                elif current_sum > target:
20                    right -= 1
21                else:
22                    return current_sum
23        
24        return closest_sum