Solution 1 - Hash Map

Use a hash map to store each number's most recent index. For each element, check if it already exists in the map and if the distance between the current index and the stored index is at most k. If so, return True. Otherwise, update the map with the current index.

TimeComplexity: O(n)

SpaceComplexity: O(n)

""" 0219.1 - Solution 1 - Hash Map Approach """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        """Contains Duplicate II Function"""
        seen = {}
        for i, num in enumerate(nums):
            if num in seen and i - seen[num] <= k:
                return True
            seen[num] = i
        return False


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().containsNearbyDuplicate([1, 2, 3, 1], 3))          # True
    print(Solution().containsNearbyDuplicate([1, 0, 1, 1], 1))          # True
    print(Solution().containsNearbyDuplicate([1, 2, 3, 1, 2, 3], 2))    # False


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 2 - Sliding Window with Set

Maintain a set of at most k elements representing a sliding window. As we iterate, check if the current element is already in the set. If so, return True. Otherwise, add it and remove the element that fell out of the window.

TimeComplexity: O(n)

SpaceComplexity: O(k)

""" 0219.2 - Solution 2 - Sliding Window with Set """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        """Contains Duplicate II Function"""
        window = set()
        for i, num in enumerate(nums):
            if num in window:
                return True
            window.add(num)
            if len(window) > k:
                window.remove(nums[i - k])
        return False


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().containsNearbyDuplicate([1, 2, 3, 1], 3))          # True
    print(Solution().containsNearbyDuplicate([1, 0, 1, 1], 1))          # True
    print(Solution().containsNearbyDuplicate([1, 2, 3, 1, 2, 3], 2))    # False


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

0219 - Contains Duplicate II

Solution 1 - Hash Map

Solution 2 - Sliding Window with Set