This problem is solved by scanning the array while maintaining a hash map of seen elements within the current sliding window of size k. For each number, check if it already exists in the hash map and if its index difference satisfies the k constraint. This approach ensures fast detection of duplicates while keeping space usage proportional to k, directly applying array scanning plus hash lookup.
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.
How GhostInterview Helps
- GhostInterview guides you to immediately use array scanning plus hash lookup for duplicates within k indices.
- It highlights when to maintain or remove elements in the sliding window to prevent incorrect results.
- The solver simulates index-based checking efficiently, showing why nested loops fail and hash lookup succeeds.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
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.
Need direct help with Contains Duplicate II instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Contains Duplicate II from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Compute the median for each sliding window of size k in an array using efficient array scanning and hash lookup techniques.
Open problem page#594 Longest Harmonious SubsequenceFind the length of the longest harmonious subsequence in an integer array using array scanning and hash-based frequency counting techniques.
Open problem page#632 Smallest Range Covering Elements from K ListsFind the minimal range covering at least one number from each of k sorted lists using array scanning and hash lookup efficiently.
Open problem page