Knowledge Guide
Home › DSA › Hashing

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:

Example 2:

Example 3:

Constraints:

Try it yourself

Try solving this question here:

✅ Solution 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 <= 105
  • -109 <= nums[i] <= 109
  • 0 <= k <= 105

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:

  1. Initialize hashmap: {}
  2. Index 0, value 7:
    • 7 is not in hashmap.
    • Add 7 to hashmap with index 0: {7: 0}
  3. Index 1, value 8:
    • 8 is not in hashmap.
    • Add 8 to hashmap with index 1: {7: 0, 8: 1}
  4. Index 2, value 9:
    • 9 is not in hashmap.
    • Add 9 to hashmap with index 2: {7: 0, 8: 1, 9: 2}
  5. 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.
Image
Image

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.
🤖 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 HashSets in Different PrograWord Pattern →