3Sum Closest

Problem Summary

• Given an array of numbers find the triplet that is the closest to the target number
• Similar to 3Sum

Main Concepts Used

• Two Pointers

Time & Space Complexity

• Time: $O(n^2)$ → Reason: Two loops
• Space: $O(1)$ → Reason: If you don't count sorting

Code

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        minSum = (float("inf"), 0)

        for i, num in enumerate(nums):  # n
            l, r = i + 1, len(nums) - 1
            while l < r:
                curSum = num + nums[l] + nums[r]
                if curSum == target:
                    return target
                elif curSum > target:
                    r -= 1
                else:
                    l += 1
                diff = abs(target - curSum)
                if diff < minSum[0]:
                    minSum = (diff, curSum)

        return minSum[1]

Common Mistakes / Things I Got Stuck On

• Forgot to sort in the code but did it in my head