Python solution with detailed explanation


  • 1
    G

    Solution

    Contains Duplicate III https://leetcode.com/problems/contains-duplicate-iii/

    Brute Force Solution

    • Brute force solution is use two loops and test both the conditions. The inner loop starts from i+1 to i+k. Because of that, we no longer need to test one of the conditions since that is taken care of automatically.
    • Time complexity : O(n * k).
    class Solution(object):
        def containsNearbyAlmostDuplicate(self, nums, k, t):
            """
            :type nums: List[int]
            :type k: int
            :type t: int
            :rtype: bool
            """
            for i in range(0, len(nums)):
                for j in range(i+1, i+k+1):
                    if j < len(nums):
                        if abs(nums[i]-nums[j]) <= t:
                            return True
            return False
    

    Binary Search Tree Solution

    • Maintain a BST of previous k elements. This is the invariant for this problem!
    • When you get element x, we want to find an element y in the BST such that (y-x)<=t or (x-y)<=t
    • How do we find (y-x)<=t ? Solution: Find the smallest value in the BST greater than or equal to x i.e. ceiling of x. Then test that value for the above condition.If the smallest value greater than x doesnt meet the criterion, then no other value y greater than x will meet the condition. One may consider the smallest element y that is greater or equal to x as the successor of x in the BST, as in: "What is the next greater value of x?"
    • How do we find (x-y)<=t? Find the greatest element y in the BST which is smaller than or equal to x. Again if this y doesnt meet the condition, no other y in the BST will meet the condition. We consider the greatest element y that is smaller or equal to x as the predecessor of x in the BST, as in: "What is the previous smaller value of x?
    • Visualize or imagine this as x and its two closest neighbors.
    • After trying the above tests, if they fail, then put x in set
    • If the size of the set is larger than k, remove the oldest item - this maintains the invariant.
    • Time complexity : O(n * log (min(n,k))). Space complexity: O(min(n,k))

    Buckets Method

    • Maintain buckets each of size t+1 holding the last k elements. This is the invariant.
    • Buckets are [0, t], [t+1,2t+1], [2t+2, 3t+2],....
    • What are the conditions of a match? Either x lies in a bucket which already has a member (this directly means that x and this element are within t of each other). Or the two neighbors of around this bucket may have a potential match. Check the code for an explanation.
    • Lastly we notice how we purge elements from the cache/buckets which are stale i.e. outside the window of k elements.
    • Notice one more thing: -3//5 = -1 - Python does this automatically and hence we dont need any special magic for handling negative numbers.
    class Solution(object):
        def containsNearbyAlmostDuplicate(self, nums, k, t):
            """
            :type nums: List[int]
            :type k: int
            :type t: int
            :rtype: bool
            """
            if t < 0:
                return False
            cache = {}
            for i in range(len(nums)):
                if i-k > 0:
                    bucket_id_to_delete = nums[i-k-1]//(t+1)
                    del cache[bucket_id_to_delete]
                bucket_id = nums[i]//(t+1)
                condition1 = (bucket_id in cache)
                condition2 = ((bucket_id-1 in cache and abs(cache[bucket_id-1]-nums[i])<= t))
                condition3 = ((bucket_id+1 in cache and abs(cache[bucket_id+1]-nums[i])<= t))
                if condition1 or condition2 or condition3:
                    return True
                cache[bucket_id] = nums[i]
            return False
    

Log in to reply
 

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