Contains Duplicate II

Easyhash-tablesliding-window
Category: Array & Hashing
Companies that ask this question:
AmazonGoogleApple
LeetCode →

Approach

Contains Duplicate II

Approach

Use hash map to track last occurrence index of each element.

Algorithm

  1. Create hash map to store num → last index
  2. For each element:
    • If seen before AND distance ≤ k: return true
    • Update last index for current element
  3. Return false if no duplicates within k distance

Complexity

  • Time: O(n) - single pass
  • Space: O(min(n, k)) - hash map size

Key Insights

  • Only need to track last occurrence, not all occurrences
  • Sliding window concept with hash map optimization

Solution

java
1class Solution {
2    public boolean containsNearbyDuplicate(int[] nums, int k) {
3        Map<Integer, Integer> seen = new HashMap<>();
4        
5        for (int i = 0; i < nums.length; i++) {
6            if (seen.containsKey(nums[i]) && i - seen.get(nums[i]) <= k) {
7                return true;
8            }
9            seen.put(nums[i], i);
10        }
11        
12        return false;
13    }
14}
Loading visualizer...