Short O(nlogn) python solution


  • -7
    Y
    class Solution:
        # @param {integer[]} nums
        # @param {integer} k
        # @param {integer} t
        # @return {boolean}
        def containsNearbyAlmostDuplicate(self, nums, k, t):
            nums = [(nums[i], i) for i in range(0, len(nums))]
            nums.sort(key=lambda x: x[0])
    
            for i in range(1, len(nums)):
                if nums[i][0] - nums[i - 1][0] <= t and abs(nums[i][1] - nums[i - 1][1]) <= k:
                    return True
            return False

  • 0
    B

    Wrong code with 1, 3, 1000, 10000, 2 as input when k = 1, t = 2

    Result should be true, but this code will return false


  • 0
    L

    The predicate nums[i][0] - nums[i - 1][0] <= t and abs(nums[i][1] - nums[i - 1][1]) <= k is wrong, as a qualified pair may not stay next to each other in the sorted (elem, pos) array.

    Yet weirdly your code can AC. So there must be something wrong with the test cases.


  • 0

    Thanks so much for pointing this out, I have just added the test case [1,3,6,2], k=1, t=2 which should prevent this common mistake.


  • 0
    Y

    thanks for pointing it out :/


Log in to reply
 

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