LeetCode 16 - 3Sum Closest

Question:

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

Answer:

The problem requires us to find a triplet of numbers in the given array, such that their sum is closest to the given target. We can use the two-pointer approach along with sorting the array to solve this problem.

Approach:

Sort the given array in non-descending order.
Initialize a variable closest_sum to store the closest sum found so far. Set it initially to the sum of first three elements in the sorted array.
Loop over the array from i=0 to i=n-3, where n is the size of the array.
For each i, initialize two pointers, left and right, to i+1 and n-1 respectively.
While left < right, calculate the sum of the current triplet, sum = nums[i] + nums[left] + nums[right].
If sum is equal to the target, we have found the closest sum possible, so we can return it immediately.
If sum is less than target, increment left by 1. This will increase the sum, and we may get a closer sum.
If sum is greater than target, decrement right by 1. This will decrease the sum, and we may get a closer sum.
After each iteration of the inner loop, check if the absolute difference between sum and target is less than the absolute difference between closest_sum and target. If it is, update closest_sum to sum.
Return closest_sum after the loop ends.

Time Complexity:

Sorting the array takes O(nlogn) time. The two-pointer approach runs in O(n^2) time. Therefore, the overall time complexity of the solution is O(n^2logn).

Space Complexity:

We are not using any extra space in the solution. Therefore, the space complexity of the solution is O(1).

Code:

class Solution(object):
    def threeSumClosest(self, nums, target):
        nums.sort()
        n = len(nums)
        closest_sum = nums[0] + nums[1] + nums[2] # initialize closest sum
        for i in range(n - 2):
            left, right = i + 1, n - 1
            while left < right: # two-pointer approach
                sum = nums[i] + nums[left] + nums[right]
                if sum == target: # sum equals target, return immediately
                    return sum
                elif sum < target:
                    left += 1
                else:
                    right -= 1
                if abs(sum - target) < abs(closest_sum - target): # update closest sum
                    closest_sum = sum
        return closest_sum