Optimizing the closest 3sum solution to avoid time limit exceeded error

user_648138 0
Viewed 110

I was going through this closest 3-sum leetcode problem which says:

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.

I have created the following solution and this appears correct but it fails with the Time Limit Exceeded error. How could I optimize this code? I have already added one of the optimization I felt but not sure how can I improve this further.

 class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()

        csum = None
        min_diff = float("+inf")

        for i in range(0,len(nums)-2):
            l = i + 1
            r = len(nums)-1
            
            if i > 0 and nums[i] == nums[i-1]:
                continue # OPTIMIZATION TO AVOID SAME CALCULATION
                
            while l < r:
                sum = nums[i] + nums[l] + nums[r]
                diff = abs(target-sum)
                if sum == target:
                    csum = target
                    min_diff = 0
                    break
                    
                elif sum > target:
                    r -= 1
                else:
                    l += 1
                    
                if min_diff > diff:
                    min_diff = diff
                    csum = sum
                
        return nums[0] if csum is None else csum
pointers arrays algorithm python
1 Answers

Maybe this reference approach can help: Try it first and see if you have any question. Note - see this from a recent post, it performs really well - exceeds 90% of submission in Python category.

 def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        return self.kSumClosest(nums, 3, target)

    def kSumClosest(self, nums: List[int], k: int, target: int) -> int:
        N = len(nums)
        if N == k:  return sum(nums[:k])     # found it

        # too small
        tot = sum(nums[:k])
        if tot >= target:  return tot

        # too big
        tot = sum(nums[-k:])
        if tot <= target: return tot
        
        if k == 1:
            return min([(x, abs(target - x)) for x in nums], key = lambda x: x[1])[0]

        closest = sum(nums[:k])
        for i, x in enumerate(nums[:-k+1]):
            if i > 0 and x == nums[i-1]:
                continue
            current = self.kSumClosest(nums[i+1:], k-1, target - x) + x
            if abs(target - current) < abs(target - closest):
                if current == target:
                    return target
                else:
                    closest = current

        return closest
user_107607680
Related