Contains Duplicate II

Difficulty: Easy | Acceptance: 51.20% | Paid: No Topics: Array, Hash Table, Sliding Window

Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.

• Examples
• Constraints
• Brute Force
• Hash Map
• Sliding Window

Examples

Example 1:

Input: nums = [1,2,3,1], k = 3
Output: true
Explanation: The duplicate 1 is found at indices 0 and 3. The distance is 3, which is <= k.

Example 2:

Input: nums = [1,0,1,1], k = 1
Output: true
Explanation: The duplicate 1 is found at indices 2 and 3. The distance is 1, which is <= k.

Example 3:

Input: nums = [1,2,3,1,2,3], k = 2
Output: false
Explanation: While there are duplicates (1 and 2), none of them are within a distance of 2 indices.

Constraints

- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
- 0 <= k <= 10^5

Brute Force

Intuition Check every possible pair of indices to see if they contain the same value and if their distance is within k.

Steps

• Iterate through the array with index i.
• For each i, iterate through indices j from i + 1 up to i + k (or the end of the array).
• If nums[i] == nums[j], return true.
• If the loops finish without finding a match, return false.

class Solution:
    def containsNearbyDuplicate(self, nums: list[int], k: int) -> bool:
        n = len(nums)
        for i in range(n):
            # Check the next k elements (or until the end of the array)
            for j in range(i + 1, min(n, i + k + 1)):
                if nums[i] == nums[j]:
                    return True
        return False

Complexity

• Time: O(n * k)
• Space: O(1)
• Notes: This approach is inefficient for large inputs where k is close to n.

Hash Map

Intuition Use a hash map to store the most recent index of each number. As we iterate, if we encounter a number that already exists in the map, we check if the distance between the current index and the stored index is <= k.

Steps

• Initialize an empty hash map.
• Iterate through the array with index i.
• If nums[i] is in the map and i - map[nums[i]] <= k, return true.
• Update the map with nums[i] and its current index i.
• If the loop finishes, return false.

class Solution:
    def containsNearbyDuplicate(self, nums: list[int], k: int) -> bool:
        seen = {}
        for i, num in enumerate(nums):
            if num in seen and i - seen[num] <= k:
                return True
            seen[num] = i
        return False

Complexity

• Time: O(n)
• Space: O(n)
• Notes: Efficient time complexity, but uses O(n) space to store the indices.

Sliding Window

Intuition Maintain a sliding window of the last k elements using a hash set. If the current element is already in the set, we found a duplicate within distance k. Otherwise, add the element to the set and remove the element that falls out of the window.

Steps

• Initialize an empty hash set.
• Iterate through the array with index i.
• If i > k, remove nums[i - k - 1] from the set (slide the window).
• If nums[i] is in the set, return true.
• Add nums[i] to the set.
• If the loop finishes, return false.

class Solution:
    def containsNearbyDuplicate(self, nums: list[int], k: int) -> bool:
        window = set()
        for i, num in enumerate(nums):
            # If the window size exceeds k, remove the oldest element
            if i > k:
                window.remove(nums[i - k - 1])
            # If current number is already in the window, we found a duplicate
            if num in window:
                return True
            window.add(num)
        return False

Complexity

• Time: O(n)
• Space: O(k)
• Notes: Optimized space complexity compared to the Hash Map approach, as it only stores at most k elements.