Need help with Python TLE, using sorted set method


  • 0
    M
    from bisect import bisect_left
    class Solution(object):
        def containsNearbyAlmostDuplicate(self, nums, k, t):
            """
            :type nums: List[int]
            :type k: int
            :type t: int
            :rtype: bool
            """
            sl = []
            for i in range(0, len(nums)):
                x = bisect_left(sl, nums[i]-t)
                if x <= len(sl) - 1 and sl[x] - nums[i] <= t:
                    return True
                bisect.insort(sl, nums[i])
                sl = list(set(sl))
                if len(sl) > k: sl.remove(nums[i-k])
            return False
                
    

    I believe the remove and insort might be causing an issue?


  • 0

    My code works.

    import bisect
    class Solution(object):
        def containsNearbyAlmostDuplicate(self, nums, k, t):
            """
            :type nums: List[int]
            :type k: int
            :type t: int
            :rtype: bool
            """
            if k == 0:
                return False
            bst = []
            if k < 0 or t < 0:
                return False
            for i, num in enumerate(nums):
                idx = bisect.bisect_left(bst, num)    
                if idx < len(bst) and abs(bst[idx] - num) <= t:
                    return True
                if idx > 0 and abs(bst[idx - 1] - num) <= t:
                    return True
                if len(bst) >= k:
                    del bst[bisect.bisect_left(bst, nums[i - k])]
                bisect.insort(bst, num)
            return False
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.