Logo
    Logo

    ©️ 2020-2026, Akhil Abraham.

    LinkedInGitHubMediumX
    Akhil Abraham
    Akhil Abraham
    /Posts
    Posts
    /LeetCode
    LeetCode
    /
    LeetCode
    /0219 - Contains Duplicate II
    0219 - Contains Duplicate II
    0219 - Contains Duplicate II
    0219 - Contains Duplicate II

    0219 - Contains Duplicate II

    Difficulty
    Easy
    Language
    Python
    URL
    https://leetcode.com/problems/contains-duplicate-ii/

    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)TimeComplexity: O(n)TimeComplexity:O(n)
    SpaceComplexity:O(n)SpaceComplexity: O(n)SpaceComplexity:O(n)

    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)TimeComplexity: O(n)TimeComplexity:O(n)
    SpaceComplexity:O(k)SpaceComplexity: O(k)SpaceComplexity:O(k)
    """ 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()

    """ 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()