16. 3Sum Closest

3Sum Closest

Problem Description

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

Explanation: The sum that is closest to the target is 0. (0 + 0 + 0 = 0).

 

Constraints:

• 3 <= nums.length <= 1000
• -1000 <= nums[i] <= 1000
• -104 <= target <= 104

This challenge is very similar to the 3-sum challenge. The main difference however is that instead of returning all possible combinations, we’re returning the closest combination (we’re actually returning the sum of the closest combination, but that’s not really important for this comparison).

Approach) Brute Force

A simple approach to solving the problem is to explore all the subsets of size 3 and keep a track of the difference between target and the sum of this subset. Then return the subset whose difference between sum and target is minimum.

for (let i = 0; i < arr.length ; i++)
{
    for(let j =i + 1; j < arr.length; j++)
    {
        for(let k =j + 1; k < arr.length; k++)
        {
            //update the closestSum
            if(Math.abs(x - closestSum) > Math.abs(x - (arr[i] + arr[j] + arr[k])))
                closestSum = (arr[i] + arr[j] + arr[k]);
        }
    }
}

return closestSum

Since we are using three nested loops, the time complexity of the above approach is O(N^3) and no extra space is required the space complexity is O(1).

Approach) Contracting Window

Just like with the 3-sum problem, this answer involves first looping through the (ordered) array of numbers. With each number, we then establish a “window”, with its left-hand side on the next number in the array, and the right-hand side on the last number.

We then check if we’ve found the solution, at which point we break out its sum. If however, the total of the 3 numbers is too low, we move the left-hand side of the window in by 1. Likewise, if the total is too high, we move the right-hand side in by 1.

In either of the above cases, we also record the total, if it is closer to the target than any previous record (as we are of course looking for the closest 3-sum here).

Let`s code it:

var threeSumClosest = function (nums, target) {
    // Store the total of the first 3 characters to be looked at (as we need a point of comparison)
    let closestToTarget = nums[0] + nums[1] + nums[nums.length - 1];

    // Sort the array
    const sortedNums = nums.sort((a, b) => a - b);

    // Loop through the array (excluding the last 2 entries)
    for (let i = 0; i < sortedNums.length - 2; i++) {
        // Establish a window from the next number to the end of the array
        let left = i + 1;
        let right = sortedNums.length - 1;

        // Run until the window is closed
        while (left < right) {
            // Add together the current number, and each side of the window
            const subTotal =
                sortedNums[left] + sortedNums[right] + sortedNums[i];

            // If we've found the answer
            if (subTotal == target) {
                return subTotal;
            }
            // If we're too low
            else if (subTotal < target) {
                left++;
            }
            // If we're too high
            else {
                right--;
            }

            // Check if this total is closer than the previous one
            if (
                Math.abs(subTotal - target) < Math.abs(closestToTarget - target)
            ) {
                // Store this total
                closestToTarget = subTotal;
            }
        }
    }
    return closestToTarget;
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem #16. 3Sum Closest

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!