174. Contains Duplicate II

Remember the most recent index where each value appeared. When you see a value again, check whether the gap to its previous position is within k. Keeping only the latest index is enough because a closer match would always come later.

Idea

We need two equal values whose indices are at most k apart. For each value it suffices to remember its most recent index: if the current occurrence isn't close enough to the last one, an even earlier one would only be farther. So a single hash map of value → last index answers every query in O(1).

Algorithm

1. Empty map last.
2. For each index i with value x:
   • If x is in last and i - last[x] <= k, return true.
   • Update last[x] = i.
3. Return false.

Worked example: nums = [1,2,3,1], k = 3

• i0: 1 → store {1:0}. i1: 2 → {..,2:1}. i2: 3 → {..,3:2}. i3: 1 → seen at 0, gap 3 - 0 = 3 <= 3 → true.

Contrast k = 2 for the same array: gap 3 > 2 → false.

Complexity

• Time: O(n).
• Space: O(min(n, k)) effectively — one entry per distinct recent value.

import java.util.HashMap;
import java.util.Map;

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, Integer> last = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (last.containsKey(nums[i]) && i - last.get(nums[i]) <= k) {
                return true;
            }
            last.put(nums[i], i);
        }
        return false;
    }
}