Given an integer array nums and an integer k, return true if there are two distinct indices i and j such that nums[i] == nums[j] and abs(i - j) <= k.

Examples

Example 1:

Input: nums = [1,2,3,1], k = 3
Output: true

Example 2:

Input: nums = [1,0,1,1], k = 1
Output: true

Example 3:

Input: nums = [1,2,3,1,2,3], k = 2
Output: false

Constraints

  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • 0 <= k <= 10^5

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Fixed-size window (this problem) O(n) O(1) Window size known upfront
Variable-size window O(n) O(1) Expand/shrink until valid
Window + hash map O(n) O(k) Track character/count frequencies
Deque window max O(n) O(k) Monotonic deque for max/min in window

Thinking Process

This extends LC 217 Contains Duplicate with a distance constraint: duplicates must be within k positions of each other.

Two approaches:

  1. Hash map – store the last seen index of each value. On a repeat, check if the distance is ≤ k.
  2. Sliding window set – maintain a set of the last k elements. If the current element is already in the window, it’s a nearby duplicate.
Sliding window a b c d e window expand right, shrink left when invalid

Approach 1: Hash Map (Last Index) – O(n)

Track the most recent index of each value. If we see the same value again and the gap is ≤ k, return true. Always update to the latest index.

Input: nums = [1,2,3,1], k = 3
Output: True
# Indices 0 and 3: nums[0] == nums[3] == 1, abs(0-3) == 3 <= 3.

Solution Explanation

Approach: Fixed-size window (this problem)

Key idea: This extends LC 217 Contains Duplicate with a distance constraint: duplicates must be within k positions of each other.

How the code works:

  1. Hash map – store the last seen index of each value. On a repeat, check if the distance is ≤ k.
  2. Sliding window set – maintain a set of the last k elements. If the current element is already in the window, it’s a nearby duplicate.

Walkthrough — input nums = [1,2,3,1], k = 3, expected output true:

  1. Initialize variables from the problem setup.
  2. Apply the main loop / recursion until the condition is met.
  3. Confirm the result matches the expected output.

    Approach 2: Sliding Window Set – O(n)

Maintain a set of size at most k. As the window slides forward, remove the element that falls out of range. If the current element is already in the window, it’s a duplicate within distance k.

Input: nums = [1,0,1,1], k = 1
Output: True
# Adjacent 1s at indices 2 and 3; abs(2-3) == 1 <= 1.

Time: O(n) Space: O(min(n, k)) – the window never exceeds size k

Comparison

Approach Time Space Advantage
Hash Map O(n) O(n) Simpler logic, stores all indices
Sliding Window Set O(n) O(min(n, k)) Better space when k ll n

Common Mistakes

  • Not updating lastIdx to the current index (keeping the first occurrence means you miss closer duplicates)
  • Off-by-one: the condition is i - j <= k, not < k
  • Forgetting to evict the oldest element from the sliding window

Key Takeaways

  • Hash map with last index is the most intuitive approach
  • Sliding window set is more space-efficient – the set acts as a fixed-size window of recent elements
  • This is a bridge problem: LC 217 (any duplicate) → LC 219 (nearby duplicate) → LC 220 (nearby + value range)

References

Template Reference