algoadvance

Leetcode 16. 3Sum Closest

Problem Statement

Given an array nums of n integers 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:

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).

Clarifying Questions

1. Input Constraints:
   • What is the range of n (size of nums)?
   • Can the array contain duplicate elements?
   • What is the range of the integer values in nums?
2. Output Guarantees:
   • Should the function return only the closest sum or the exact sum if it matches the target?

Strategy

1. Sort the Array:
   • Begin by sorting the array. This allows us to efficiently find the closest sum using a two-pointer technique.
2. Iterate and Use Two Pointers:
   • Iterate through each element, and for each element, use two pointers to find the close sum for the remaining elements.
   • Calculate and update the closest sum during each iteration.
3. Update the Closest Sum:
   • If the current three-sum is closer to the target than the previously recorded closest sum, update the closest sum.
   • Adjust the pointers based on the comparison with the target to efficiently narrow down the closest sum.
4. Terminate Early:
   • If you find an exact match (current_sum == target), you can immediately return because you can’t get closer than an exact match.

Code

#include <vector>
#include <algorithm>
#include <cstdlib> // for abs()

using namespace std;

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int closestSum = nums[0] + nums[1] + nums[2]; // Initial assumption with first three elements

        for (size_t i = 0; i < nums.size() - 2; ++i) {
            size_t left = i + 1;
            size_t right = nums.size() - 1;

            while (left < right) {
                int currentSum = nums[i] + nums[left] + nums[right];

                // Update the closestSum if the currentSum is closer to the target
                if (abs(currentSum - target) < abs(closestSum - target)) {
                    closestSum = currentSum;
                }

                if (currentSum < target) {
                    ++left;
                } else if (currentSum > target) {
                    --right;
                } else {
                    // If currentSum equals target, we've found the closest possible sum
                    return currentSum;
                }
            }
        }

        return closestSum;
    }
};

Time Complexity

• Sorting: (O(n \log n)) because we sort the array initially.
• Two-pointer traversal: (O(n^2)) because for each element, we traverse the rest of the array using two pointers.

Thus, the overall time complexity is (O(n^2)), where (n) is the size of the input array nums.

Final Notes

• This approach efficiently narrows down the closest sum using sorting combined with the two-pointer technique.
• It guarantees a solution with time complexity manageable for reasonably large inputs.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?