easy Contains Duplicate II

Problem Statement

Given an array of integers nums and an integer k, return true if there are any two different indices i and j in the array where nums[i] == nums[j] and abs(i - j) <= k. Otherwise, return false.

Examples

Example 1:

Input: nums = [10, 20, 10, 30], k = 1
Output: false
Explanation: The number 10 appears at positions 0 and 2. The difference between these positions is 2, which is not less than k.

Example 2:

Input: nums = [5, 15, 25, 5, 35], k = 3
Output: true
Explanation: The number 5 appears at positions 0 and 3. The difference between these positions is 3, which is equal to k.

Example 3:

Input: nums = [7, 8, 9, 7, 10, 11], k = 4
Output: true
Explanation: The number 7 appears at positions 0 and 3. The difference between these positions is 3, which is less than to k.

Constraints:

1 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹
0 <= k <= 10⁵

Try it yourself

Try solving this question here:

🎯 STRICT STANDOUT: Why / worked+complexity / pattern+when-not / edge / drills — Contains Duplicate II easy

Why this concept exists (judgment layer)

This is near-duplicate detection with a distance budget k — not plain Contains Duplicate. The pattern cue is "same value within index distance k" → sliding membership window or last-index map, not full-array sort alone.

Worked example with complexity derivation

nums=[5,15,25,5,35], k=3:
Last-index map: 5→0,15→1,25→2; at i=3 val5 last=0, 3-0=3≤k → true.
nums=[10,20,10,30], k=1: at second 10, 2-0=2>1 update last; no hit → false.
Constraints n≤1e5 ⇒ O(n) required; O(n²) pair scan fails.
Sliding HashSet of size ≤k: add nums[i]; if size>k remove nums[i-k]; add fails on dup in window.

Pattern + when-NOT / named alternative

PATTERN: last-seen index HashMap OR fixed-size-k HashSet sliding window. WHEN NOT: k≥n-1 → reduces to ordinary Contains Duplicate (any dup). WHEN NOT sort-only: sorting loses indices unless you pair (value,index) — usually worse than hash O(n). Two pointers on unsorted array wrong.

Edge case / failure mode

Edges: k=0 → always false (need different indices); n=1; negatives; duplicates far then near (always update last index). Empty not in constraints but return false.

Hostile-panel drills (defend the decision)

Q1. Why update map even when i-last > k?
Model answer: Later indices may form a closer pair with the newest occurrence.

Q2. Set-window vs last-index map?
Model answer: Set of last k values: O(min(n,k)) space strict window; map stores one index per value — also O(n) worst but simple.

Q3. Trace [1,2,3,1] k=3.
Model answer: Last 1 at 0; i=3 → 3-0=3≤3 true.

✅ Solution Contains Duplicate II

Problem Statement

Examples

Example 1:

Input: nums = [10, 20, 10, 30], k = 1
Output: false
Explanation: The number 10 appears at positions 0 and 2. The difference between these positions is 2, which is not less than k.

Example 2:

Input: nums = [5, 15, 25, 5, 35], k = 3
Output: true
Explanation: The number 5 appears at positions 0 and 3. The difference between these positions is 3, which is equal to k.

Example 3:

Input: nums = [7, 8, 9, 7, 10, 11], k = 4
Output: true
Explanation: The number 7 appears at positions 0 and 3. The difference between these positions is 3, which is less than to k.

Constraints:

1 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹
0 <= k <= 10⁵

Solution

To solve this problem, we'll use a hashmap to keep track of the last seen position of each number as we iterate through the array. This approach is efficient because it allows us to check in constant time whether a number has appeared before and whether the difference between the current position and the last seen position is less than or equal to k. By using a hashmap, we ensure that we only traverse the array once, making our solution fast.

This approach is effective because it minimizes the number of operations required to find the solution, ensuring that we can handle large arrays efficiently.

Step-by-step Algorithm

Initialize an empty hashmap to store the last seen position of each number.
Loop through the array with an index i.
- For each number nums[i], check if it is already in the hashmap.
  - If it is, check if the difference between the current index i and the stored index is less than or equal to k.
    - If true, return true.
  - If it is not, or the difference is greater than k, update the hashmap with the current index.
If the loop completes without finding any valid pairs, return false.

Algorithm Walkthrough

Using the input nums = [7, 8, 9, 7, 10, 11], k = 4:

Initialize hashmap: {}
Index 0, value 7:
- 7 is not in hashmap.
- Add 7 to hashmap with index 0: {7: 0}
Index 1, value 8:
- 8 is not in hashmap.
- Add 8 to hashmap with index 1: {7: 0, 8: 1}
Index 2, value 9:
- 9 is not in hashmap.
- Add 9 to hashmap with index 2: {7: 0, 8: 1, 9: 2}
Index 3, value 7:
- 7 is in hashmap at index 0.
- Check difference: 3 - 0 = 3, which is less than or equal to k.
- Return true.

Code

java

import java.util.HashMap;

class Solution {

  public boolean containsNearbyDuplicate(int[] nums, int k) {
    // Create a hashmap to store the last seen index of each number
    HashMap<Integer, Integer> map = new HashMap<>();

    // Loop through the array
    for (int i = 0; i < nums.length; i++) {
      // Check if the current number has been seen before
      if (map.containsKey(nums[i])) {
        // Check if the difference between indices is less than or equal to k
        if (i - map.get(nums[i]) <= k) {
          return true;
        }
      }
      // Update the last seen index of the current number
      map.put(nums[i], i);
    }

    // If no such pair is found, return false
    return false;
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    System.out.println(
      solution.containsNearbyDuplicate(new int[] { 10, 20, 10, 30 }, 1)
    ); // false
    System.out.println(
      solution.containsNearbyDuplicate(new int[] { 5, 15, 25, 5, 35 }, 3)
    ); // true
    System.out.println(
      solution.containsNearbyDuplicate(new int[] { 7, 8, 9, 7, 10, 11 }, 4)
    ); // true
  }
}

Complexity Analysis

Time Complexity: , where n is the number of elements in the array. We traverse the array once, and each operation (insert and lookup in the hashmap) takes time.
Space Complexity: , where n is the number of elements in the array. In the worst case, all elements are stored in the hashmap.

🎯 STRICT STANDOUT: Why / worked+complexity / pattern+when-not / edge / drills — Solution Contains Duplicate II

Why this concept exists (judgment layer)

Solution stores last index per value: one pass, O(1) check distance. Elevates from recipe to decision: why map beats nested loops at n=1e5, and how window-set is the dual form.

Worked example with complexity derivation

nums=[7,8,9,7,10,11], k=4 (page walkthrough):
map {} →{7:0}→{7:0,8:1}→{…9:2}; i=3 val7, 3-0=3≤4 → true.
Time: single loop n map ops → O(n) average; space O(min(n, distinct)).
Wrong: if skip map.put when far, later pair with old index may miss nearer dup.
Code always put after check — correct.

Pattern + when-NOT / named alternative

PATTERN name: LAST-INDEX HASHMAP (near-duplicate window). Recognition: equal values + |i-j|≤k. WHEN NOT: no k constraint → HashSet any-dup; need sorted stream → sort pairs. Not two-pointer on unsorted. Sliding HashSet if you prefer explicit forget-at-i-k.

Edge case / failure mode

Hand-run edge: [1,2,1], k=1 → at i=2, 2-0=2>1, put 1→2, false. k=0 any: false. All unique: false. Negatives as keys OK.

Hostile-panel drills (defend the decision)

Q1. Complexity with derivation.
Model answer: for i in 0..n-1: O(1) avg contains/get/put → Θ(n) time; map ≤n keys → O(n) space.

Q2. Is worst-case hash O(n²)?
Model answer: Pathological collisions can degrade; rare with library hashes; state average O(n).

Q3. Dual window-set algorithm in one sentence.
Model answer: Maintain set of values in (i-k,i]; on add failure return true; evict nums[i-k].

🧩 Pattern · Hashing

Recognize it: Membership / frequency / “have I seen this?” in O(1) → a hash map or set.

▶ Visualize this problem (step it, predict each fork)

⛶ Open this problem debugger in explore mode

🤖 Don't fully get this? Learn it with Claude

Stuck on Contains Duplicate II? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Contains Duplicate II** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Contains Duplicate II** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Contains Duplicate II**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Contains Duplicate II**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Using Hashtable in Different Progr Word Pattern →