LC 219

Solution to LeetCode 219 Contains Duplicate II.

LeetCode 219

Contains Duplicate II (Easy). [link]

1. HashTable. 1) if there is a number in hash such that i-j <= k, return True. 2) if not in hash, add its index to the hash. Time complexity O(N). Space complexity O(N).

class Solution(object):
    def containsNearbyDuplicate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """
        hash = {}
        for i, num in enumerate(nums):
            if num in hash and i - hash[num] <= k:
                return True
            hash[num] = i
        return False

2. Sliding window. Find a sliding window with size < (k+1) such that it contains duplicated numbers. Time complexity O(N). Space complexity O(K).

class Solution(object):
    def containsNearbyDuplicate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """
        s = set() # sliding window
        for i, num in enumerate(nums):
            if i > k:
                s.remove(nums[i - k - 1])
            if num in s:
                return True
            s.add(num)
        return False

class Solution(object):
    def containsNearbyDuplicate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """
        hash = {} 
        start, end = 0, 0 # sliding window
        for end in range(len(nums)):

            if nums[end] not in hash:
                hash[nums[end]] = 1
            else:
                return True
            
            if end - start + 1 > k:
                del hash[nums[start]]
                start += 1
        return False