#219

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Contains Duplicate II

Check if any two equal numbers exist within k indices using array scanning and hash table lookup efficiently.

Problem Statement

Given an integer array nums and an integer k, determine if there exist two distinct indices i and j such that nums[i] equals nums[j] and the absolute difference between i and j is at most k. Return true if such a pair exists; otherwise, return false.

You must implement a solution that efficiently handles large arrays, leveraging hash-based lookup and a sliding window approach to detect duplicates within k positions. For example, with nums = [1,2,3,1] and k = 3, the function should return true because nums[0] and nums[3] are equal and their indices differ by 3.

Examples

Example 1

Input: nums = [1,2,3,1], k = 3

Output: true

Example details omitted.

Example 2

Input: nums = [1,0,1,1], k = 1

Output: true

Example details omitted.

Example 3

Input: nums = [1,2,3,1,2,3], k = 2

Output: false

Example details omitted.

Constraints

1 <= nums.length <= 105
-109 <= nums[i] <= 109
0 <= k <= 105

Solution Approach

Hash Map Sliding Window

Iterate through nums while maintaining a hash map of numbers mapped to their latest index. If a number already exists in the map, check the index difference. Remove numbers from the map when their index is outside the k-window to maintain the sliding window property.

Set-based Window

Maintain a set of the last k elements. For each element, check if it exists in the set. If yes, return true. Otherwise, add it to the set and remove the oldest element when the window exceeds k, which ensures O(n) time and O(k) space.

Direct Comparison (Inefficient for Large Arrays)

For completeness, a brute-force approach scans all pairs of indices i and j, checking nums[i] == nums[j] and abs(i-j) <= k. This has O(n*k) time and fails for large arrays, illustrating why hash lookup is crucial for this problem pattern.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) for the hash map or set sliding window approach because each element is processed once and hash operations are O(1). Space complexity is O(min(n,k)) as only the most recent k elements are stored in the hash map or set, keeping memory proportional to the sliding window.

What Interviewers Usually Probe

Do you understand why a hash map is necessary instead of nested loops?
Notice how the sliding window maintains the k-index constraint efficiently.
Ask if the solution handles edge cases like k = 0 or all unique elements.

Common Pitfalls or Variants

Common pitfalls

Using nested loops blindly leads to TLE on large arrays.
Failing to remove elements outside the k-window from the map or set breaks correctness.
Confusing the requirement for indices versus values can result in false positives.

Follow-up variants

Check for duplicates within k distance but allow a value to repeat multiple times; count total pairs.
Find the first duplicate within k indices and return its pair of indices instead of true/false.
Extend the problem to handle multiple k values dynamically for streaming input arrays.

FAQ

What is the core pattern in Contains Duplicate II?

The core pattern is array scanning combined with hash-based lookup within a sliding window of size k to detect nearby duplicates.

Can this problem be solved without a hash map?

Yes, using a set to maintain a window of size k works, but brute-force comparisons fail for large arrays.

What happens if k is 0?

No duplicates can satisfy abs(i-j) <= 0 except at the same index, which is invalid, so the result is always false.

How does sliding window optimize space?

It keeps only the last k elements in memory, so space is limited to O(k) instead of O(n).

Why does GhostInterview suggest removing old elements from the map?

Removing elements outside the k-window prevents false positives and ensures the solution correctly respects the index constraint.

terminal

Solution

Solution 1: Hash Table

We use a hash table $\textit{d}$ to store the recently traversed numbers and their corresponding indices.

1

2

3

4

5

6

7

8

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

Continue Practicing

#480 sliding window median #594 longest harmonious subsequence #632 smallest range covering elements from k lists