DKodeTree Small Logo
DKodeTreeWhere logic takes root...!
Contains Duplicate II - Solution
Solutions and explanations
Link to Problem StatementView on GitHubWatch Video

Video Explanation

This is a one-pass solution that uses a hash map to store the last seen index of each number.

  • If a number reappears within k indices of its previous occurrence, it returns True.
  • Otherwise, it updates the stored index for that number.
  • If no such duplicate is found by the end of the loop, it returns False.
class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        index_map = {}
        for idx, num in enumerate(nums):
            if num in index_map and idx - index_map[num] <= k:
                return True
            index_map[num] = idx
        return False

Complexity Analysis

Here, n is the input size.

  • Time Complexity: O(n)
  • Space Complexity: O(n)

This is a one-pass sliding window solution, with a window size of k, that uses a hash set to track the last k elements.

  • If the current number is already in the window, a nearby duplicate exists, so it returns True.
  • Otherwise, the number is added to the window.
  • If the window exceeds size k, the leftmost element is removed to maintain the correct range.
  • If no nearby duplicates are found by the end, it returns False.
class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        window = set()
        left = 0

        for num in nums:
            if num in window:
                return True
            window.add(num)
            if len(window) > k:
                window.remove(nums[left])
                left += 1
        return False

Complexity Analysis

Here, n is the number of elements in the input list, and k is a given input value that represents the size of the sliding window in this solution.

  • Time Complexity: O(n)
  • Space Complexity: O(k)