[Top Interview 150] 219. Contains Duplicate II

Solution)

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        window = {}
        window[nums[0]] = 0

        l, r = 0, 1

        while r < len(nums) and l < r:
            if r-l <= k:
                if nums[r] in window:
                    return True
                
                window[nums[r]] = r
                r += 1
            else:
                del window[nums[l]]
                l += 1
        
        return False

 
Problem: LeetCode
 
Time Complexity: O(n)
Space Complexity: O(n)

Explanation)

We're going to use a sliding window with a dictionary.
 
First, we'll make a window that has a length of k+1 by adding elements to a dictionary while checking if there exists a duplicate.
 
If we didn't find a duplicate even after making a window, then we'll slide the window to the right by one until we find a duplicate. We'll slide the window by adding and deleting an element inside a dictionary.
 
If we can't find a duplicate until the end of nums, we'll simply return False.

Initialization)

To implement a sliding window, we'll use a dictionary to save the elements that exist inside the window.
And because the problem says that there is at least one element in nums, we'll add the first element inside the dictionary.
 
We'll also use two pointers that will mark the ends of the window.
 

def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        window = {}
        window[nums[0]] = 0

        l, r = 0, 1

Expanding Window)

We'll expand the window until the maximum of r-l becomes k. 
 
While expanding the window, if we're lucky enough to find a duplicate inside the window, we'll immediately return True.
If we don't find a duplicate, we'll keep on expanding.
 

def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        window = {}
        window[nums[0]] = 0

        l, r = 0, 1

        while r < len(nums) and l < r:
            if r-l <= k:
                if nums[r] in window:
                    return True
                
                window[nums[r]] = r
                r += 1

After Expansion)

While adding a new element in the dictionary, there will be a case where the size of the window exceeds the required size.
 
To fix this, we'll delete the first item in the window and increase l by 1. By doing so, the condition r-l <= k is accomplished again, so we'll be able to check if the newest element added in a dictionary has a duplicate in a dictionary.
 
If the while loop is completed without finding a duplicate, we'll return False.
 

def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        window = {}
        window[nums[0]] = 0

        l, r = 0, 1

        while r < len(nums) and l < r:
            if r-l <= k:
                if nums[r] in window:
                    return True
                
                window[nums[r]] = r
                r += 1
            else:
                del window[nums[l]]
                l += 1
        
        return False

 
 
I was wondering why this problem was categorized under hashmap. I thought I could do a sliding window without extra memory. Then I realized you need some kind of memory to save the elements inside the window to check if there exists a duplicate. Since you can find an element in a dicionary faster than a list, it's better to use a dictionary.