16. 3Sum Closest

MediumLeetCode

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 <= 500
• -1000 <= nums[i] <= 1000
• -10^4 <= target <= 10^4

How to solve the problem

• Sorting the array nums first to use two pointer approach.
• Use three pointers: one for the first element, and two pointers for the remaining two elements.
• Keep track of the closest sum found so far and update it when a closer sum is found.

Code

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        n = len(nums)
        result = inf
        for k in range(2,n):
            left = 0
            right = k -1
            while left < right:
                current_sum = nums[left] + nums[right] + nums[k]
                if current_sum == target:
                    return current_sum
                if abs(current_sum - target) < abs(result - target):
                    result = current_sum
                if current_sum > target:
                    right -= 1
                else:
                    left += 1
        return result

Complexity

Time complexity: O(n²)

• Traversing nums[k] is O(n), two pointer is O(n), so in total is O(n²).

Space complexity: O(1)

• We ignore the memory required for the output. For the purpose of complexity analysis, we also ignore sorting algorithm.