16. 3Sum Closest — LeetCode(Python)

I got you!

Problem:

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

Constraints:

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

Solution:

nums.sort()
res = nums[0] + nums[1] + nums[2]
        
for i in range(len(nums)-2):
    l, r = i+1, len(nums)-1
    while l < r:
        s = nums[i] + nums[l] + nums[r]
        if s == target:
            return s
        if abs(s - target) < abs(res - target):
            res = s
        if s < target:
            l += 1
        else:
            r -= 1
                    
return res

Explanation —

This problems is a version of 3Sum on LeetCode. Here, instead of finding all triplets that give us a sum of target, we are only asked to find the triplet with sum closest to target.

Since we can assume that there is always only one solution, our task becomes easier.

We use a two-pointer approach here.

First, we sort our list. Then we iterate over the numbers sequentially.

During, each iteration, we initialize two pointers — one on the next index and other at the end of the list.

We then, calculate the sum of nums[i], nums[l] and nums[r].

If this sum is equal to the target, we return this sum.

If this sum is closer to our target value than any previous sum, we change our res variable to sum.

If it is less than the target value, we increment our left pointer since we know that the list is sorted. Otherwise, we decrement our right pointer.

The final list is then returned.

Time and Space Complexity —

Sorting the list takes O(nlogn) time and our algorithm requires us to visit each element in the array twice on average, leading us to require quadratic time.

The space complexity depends on our sorting algorithms and can be either linear or constant.

Thus, if n is the length of the array nums,

Time Complexity: O(n²)

Space Complexity: O(1) or O(n)

Feel free to ask any related questions in the comment section or the links provided down below.

I don’t have friends:

Let’s be friends!

Connect with me on:

LinkedIn

GitHub

Instagram (I know. Very professional)

Jai Shri Ram 🙏