Skip to main content

219. Contains Duplicate II

Problem

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.

217. Contains Duplicate​

LeetCode

Solution

219. Contains Duplicate III​

LeetCode

Solution​

Runtime: 100 ms, faster than 60.47% of Python3 online submissions for Contains Duplicate II. Memory Usage: 21.6 MB, less than 34.55% of Python3 online submissions for Contains Duplicate II.

Similar Algorithm to 217. Contains Duplicate, using set.

One iteration through the list is enough.

Since the difference can be at most k, so we can update the index whenever we see a new occurrence.

Time Complexity: O(n)

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        table = {}
        for i in range(len(nums)):
            if nums[i] in table and abs(i - table[nums[i]]) <= k:
                return True
            table[nums[i]] = i
        return False

Sliding Window Through Hash Set​

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        seen = set()
        for i in range(len(nums)):
            if nums[i] in seen:
                return True
            seen.add(nums[i])
            if len(seen) > k:
                seen.remove(nums[i - k])
        return False