Three-Sum Closest

Patrick Leaton
Published: June 19, 2021, 3:39 p.m.
Problem Description

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

 

Constraints:

  • 3 <= nums.length <= 10^3
  • -10^3 <= nums[i] <= 10^3
  • -10^4 <= target <= 10^4

 

The description was taken from https://leetcode.com/problems/3sum-closest/.

Problem Solution

#O(N^2) Time, O(1) Space
class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        if len(nums)==3:
            return sum(nums)
        nums.sort()
        closest = 3*(10**3+1)
        for left in range(0, len(nums)-2):
            mid, right = left+1, len(nums)-1
            while mid < right:
                current = nums[left]+ nums[mid]+ nums[right]
                if current < target:
                    mid += 1
                elif current > target:
                    right -= 1
                else:
                    return current
                if abs(current-target) < abs(closest-target):
                    closest = current
        return closest

Problem Explanation

First off, this question is exactly the same as Three-Sum, but with one exception.  Instead of finding the three numbers that sum to the target number, we will instead be finding the three numbers whose absolute difference from the target is less than all of the other number combinations.  

With that being said, we will use three pointers from two nested loops.  One pointer will be an anchor number that will exist within the outer loop.  The other two pointers from the inner loop will try to combine with that pointer in an attempt to sum closest to the target.  If we come across the actual target, we will return the three-number combination that summed to it.  If not, we will return the closest combination we got to it, which will be the combination with the lowest absolute difference from it.

First off, if we only have three numbers then these are the only numbers that we can make a combination from.

In this case, we will return the sum of these three.

        if len(nums)==3:
            return sum(nums)

 

Next, we will sort the input array.

By doing this, we will be able to move the last two pointers in an iterative, binary search-like fashion and continue getting close to the target.

        nums.sort()

 

After, we will create our closest variable that we will initialize to three times ten to the third power plus one. 

This seems like a random number, but this is a good number to use because the description says the range of each number could vary up to ten to the third power.  By making each three numbers just one more, we can guarantee we won't be starting with a number that could exist inside an actual test case and get the wrong answer.  We could use the infinity float value instead, but this shows we are paying attention to the constraints.

        closest = 3*(10**3+1)

 

Then, we will create our left iterator that will only go up to one number from the last index of the input array.

The reason being we will want to be able to fit a middle and a right pointer past it within the last iteration if we need to so that we can also try the last three numbers of the array for the sum closest to the target.

        for left in range(0, len(nums)-2):

 

Now that we have our left pointer, we will make a mid pointer one index past the left, and a right pointer at the last index of the array.

            mid, right = left+1, len(nums)-1

 

Then, while the mid and the right pointer haven't crossed each other (the left pointer is stuck where it is), we will continue searching the current window for the three best numbers.

            while mid < right:

 

At the beginning of each iteration, we will sum the three current numbers.

                current = nums[left]+ nums[mid]+ nums[right]

 

If the current sum is less than the target, we will move the mid pointer to the right so we can get a higher sum combination within the next iteration.

                if current < target:
                    mid += 1

 

If the current sum is greater than the target, we will move the right pointer to the left so we can get a lower sum combination within the next iteration.

                elif current > target:
                    right -= 1

 

Otherwise, this combination sums to the target, so we will stop and return it because we can't get any closer from here.

                else:
                    return current

 

At the end of each iteration, we will test the absolute difference from the current combination's sum against the target, then compare that to the closest combination we have seen so far.  If the current sum is closer, we will make it the new closest sum.

                if abs(current-target) < abs(closest-target):
                    closest = current

 

Once we have tried to combine two numbers with each number from the input array, we will return the closest sum to the target that we were able to get.

        return closest