LeetCode 16 Solution - 3Sum Closest

Problem Statement (LeetCode 16)

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

Example 2:

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

---

Optimal Approach: Sorting + Two Pointers

Intuition

1. Sorting: Sorting the array helps in applying the two-pointer technique effectively, allowing us to reduce the problem size.
2. Greedy Search for Closest Sum: For each element in the array, use two pointers (left and right) to find the closest sum to the target. Adjust the pointers based on the sum's proximity to the target.

Why This Approach Works

• Efficiency: Sorting the array first (O(n log n)) allows us to apply the two-pointer technique for each fixed element, reducing the complexity from O(n^3) to O(n^2).
• Greedy Adjustment: By evaluating the sum and adjusting the pointers based on whether the sum is less than or greater than the target, we move towards the closest sum.
• Time Complexity: The approach runs in O(n^2) time due to the sorting step and the two-pointer iteration.

---

LeetCode-Compatible C++ Code

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());  // Sort the array to use the two-pointer technique
        
        int closestSum = INT_MAX;  // Initialize the closest sum with a large value
        
        for (int i = 0; i < nums.size(); ++i) {
            // Skip duplicate elements to avoid redundant checks
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            
            int left = i + 1, right = nums.size() - 1;
            
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                
                // Update the closest sum if the current sum is closer to the target
                if (abs(sum - target) < abs(closestSum - target)) {
                    closestSum = sum;
                }
                
                if (sum < target) {
                    ++left;  // Move left pointer to the right to increase the sum
                } else if (sum > target) {
                    --right;  // Move right pointer to the left to decrease the sum
                } else {
                    return sum;  // If the sum equals the target, return the sum immediately
                }
            }
        }
        
        return closestSum;
    }
};

---

Step-by-Step Explanation of Code

1. Sorting the Array:
   We begin by sorting the input array to make use of the two-pointer technique, which allows us to find the closest sum more efficiently.

2. Iterating Over Each Element (i):
   We fix the first element (nums[i]) and search for two numbers that together form the closest sum. We skip duplicate elements to avoid unnecessary duplicate checks.

3. Two Pointers (left and right):
   For each fixed element, we initialize two pointers: left starting from the element just after i and right starting from the end of the array. The idea is to find pairs such that the sum of nums[i] + nums[left] + nums[right] is closest to the target.

4. Updating the Closest Sum:
   We calculate the sum of the three numbers and check if it's closer to the target than the previously found closest sum. If it is, we update the closestSum.

5. Adjusting Pointers:
   Based on the current sum:

   • If the sum is less than the target, move the left pointer to the right to increase the sum.
   • If the sum is greater than the target, move the right pointer to the left to decrease the sum.
   • If the sum equals the target, return the sum immediately as it’s the closest possible sum.

6. Returning the Closest Sum:
   After processing all possible triplets, we return the closest sum found.

---

Dry Run with Example

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

Step 1: Sort the array: [-4, -1, 1, 2]

Step 2: Iterate through the array with the index i.

• For i = 0 (element -4):

  • left = 1, right = 3: Sum = -4 + (-1) + 2 = -3 (closest sum: -3)
  • Move left to the right.
  • For left = 2, right = 3: Sum = -4 + 1 + 2 = -1 (closest sum: -1)
  • Move left to the right.
  • For left = 3, right = 3: Loop ends.

• For i = 1 (element -1):

  • left = 2, right = 3: Sum = -1 + 1 + 2 = 2 (closest sum: 2)
  • Move right to the left.
  • For left = 2, right = 2: Loop ends.

Step 3: Return the closest sum: 2

---

Alternative Approaches & Why Not?

Approach	Time Complexity	Space Complexity	Why Not?
Brute Force (Triple Nested Loop)	O(n^3)	O(1)	This approach checks all triplets, which is inefficient for large input arrays.
Sorting + Binary Search	O(n^2 log n)	O(1)	Binary search introduces unnecessary complexity.
Sorting + HashMap	O(n^2)	O(n)	Requires extra space for the HashMap, making it less efficient than the two-pointer approach.

---

Why Two-Pointer Approach is the Best

• Time Complexity is O(n^2): The sorting step takes O(n log n), and the two-pointer iteration runs in O(n), leading to a time complexity of O(n^2).
• Space Complexity is O(1): We don't require any extra space except for the result.
• Efficient for Finding the Closest Sum: The two-pointer approach efficiently narrows down the best sum by adjusting pointers based on the current sum's proximity to the target.

---

Complexity Analysis

• Time Complexity: O(n^2)
  Sorting takes O(n log n), and the two-pointer approach inside the loop runs in O(n), resulting in a total time complexity of O(n^2).

• Space Complexity: O(1)
  The space complexity is constant as we only store the result and use a few variables for iteration.

---

Conclusion

✅ Best Approach: Sorting + Two Pointers
✅ Time Complexity: O(n^2)
✅ Space Complexity: O(1)
✅ Optimal Solution for the Problem

Recommended Problems for Practice

1. 3Sum
2. Two Sum II - Input Array Is Sorted
3. 3Sum Smaller

🚀 Master the 3Sum Closest Problem with Two Pointers!