Loading…

easyArraysLC #219Frequently asked

Contains Duplicate II

Arrays & Hashing · 16 of 83 · 8 min

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

In plain English

We need two equal values whose positions are at most k apart. It is not enough for a value to repeat — the repetition must happen within a sliding index window of width k. With k ≥ array length this degenerates to plain 'are there any duplicates'; with k = 0 it is always false.

Examples

Example 1

Input: nums = [1, 2, 3, 1], k = 3
Output: true
Note: The two 1's are at indices 0 and 3; |0 - 3| = 3 ≤ 3.

Example 2

Input: nums = [1, 0, 1, 1], k = 1
Output: true
Note: The 1's at indices 2 and 3 are distance 1 apart ≤ 1. (The 0/2 pair is too far, but the closest pair wins.)

Example 3

Input: nums = [1, 2, 3, 1, 2, 3], k = 2
Output: false
Note: Every repeated value is exactly distance 3 apart, which exceeds k = 2.

Example 4

Input: nums = [99, 99], k = 0
Output: false
Note: Distinct indices 0 and 1 have gap 1 > 0. k = 0 can never match.

Constraints

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

Clarifying questions4First question: Is the distance condition |i - j| <= k inclusive of k?Explore questions

Q1.Is the distance condition |i - j| <= k inclusive of k?
Yes, ≤ k. A gap of exactly k counts as a match. I'll use <= rather than <.
Q2.What happens when k is 0?
Two distinct indices have a gap of at least 1, which can never be ≤ 0, so the answer is always false. The code handles it naturally without a special case.
Q3.Can values be negative or very large?
Yes, up to ±10⁹, so I'll key the hash map by the integer value directly — no array-indexing tricks that assume a small non-negative range.
Q4.If k exceeds the array length, does it just become Contains Duplicate?
Effectively yes — every pair is within distance k, so any duplicate at all returns true. Both my solutions handle that without a branch.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Return true if there exist two equal values within index distance k — i.e. nums[i] == nums[j] and |i − j| ≤ k. The clean answer is a hash map of value → most-recent index: when you re-see a value, check if the gap to its last index is ≤ k. Equivalently, slide a window of size k holding a set of the last k values. Both are O(n) time; the window is O(min(n, k)) space.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you fold the index-distance constraint into a hash map cleanly — specifically whether you realize you should keep the MOST RECENT index of each value, not the first.

Where candidates slip

Storing the first occurrence index and never updating it, which can report a gap larger than k even when a closer pair exists; or using strict < k instead of <= k.

How to stand out

Offer both the value→last-index map and the fixed-size sliding-window set, explain the space trade-off, and connect it forward to Contains Duplicate III's value-window generalization.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Hash Map of Last Index (Optimal, simplest)Optimal	`O(n)`	`O(n)`	Lead with this — it's the cleanest. Stress 'I keep the MOST RECENT index of each value'.	Read
2	Sliding Window — Set of the Last k Values	`O(n)`	`O(min(n, k))`	Bring up when the interviewer asks to bound memory: this caps space at O(min(n, k)) instead of O(n).	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewFind equal values within distance kCare about memory bound?NoYes, cap at kExplore the full tree

value → last index on [1,2,3,1], k=3nums = [1, 2, 3, 1], k = 3

How to read it:Each frame is the map after one step. The repeat of 1 finds last index 0; gap 3 ≤ 3 → true.

Frame 1
i=0, x=1
1 unseen → store 1→0
1→ 0
Frame 2
i=1, x=2
2 unseen → store 2→1
1→ 0
2→ 1
Frame 3
i=2, x=3
3 unseen → store 3→2
1→ 0
2→ 1
3→ 2
Frame 4
i=3, x=1
1 seen at 0, gap 3 ≤ 3 → return true
1→ 0
2→ 1
3→ 2
Match found.

Just inserted / updatedLooking upMatch

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2 · Optimal

Hash Map of Last Index (Optimal, simplest)

TimeO(n)SpaceO(n)

Lead with this — it's the cleanest. Stress 'I keep the MOST RECENT index of each value'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Plain Contains Duplicate uses a set: 'have I seen x before?'. Here you also need to know HOW LONG ago. What should the map's value be so you can answer that?

2Hint 2Explore hint

Map value → the last index where it appeared. When you re-see x, the gap is i − last[x]; if that's ≤ k you're done.

3Hint 3Explore hint

Crucially, always overwrite last[x] = i, even when the gap was too big — the nearest previous occurrence gives the smallest possible future gap.

A · Core idea

Walk the array once, maintaining a hash map from each value to the most recent index at which it occurred. At position i with value x, if x is already in the map and i − last[x] ≤ k, we've found a qualifying pair and return true. Otherwise we update last[x] = i and continue.

Why 'most recent index' and not 'first index'. This is the subtle heart of the problem. Suppose x appears at indices 0, 4, and 5 with k = 1. If we stored only the first index 0 and never updated it, then at index 4 we'd compute gap 4 > 1 (no match) and at index 5 gap 5 > 1 (no match) — and wrongly conclude false, even though indices 4 and 5 are distance 1 apart. By always overwriting last[x] with the current index, the comparison at index 5 uses last[x] = 4, giving gap 1 ≤ 1 → true. The nearest previous occurrence is always the one most likely to satisfy the distance bound, so keeping it is both correct and optimal.

Why this reduces to Contains Duplicate when k is large. If k ≥ n − 1, then any repeat has a gap ≤ k, so the first time we ever re-see a value we return true — exactly plain Contains Duplicate. The distance check simply never rejects. This is a good sanity check to mention: Contains Duplicate II strictly generalizes Contains Duplicate, with k = ∞ recovering the original.

Why `≤ k` and why k = 0 is automatically false. Two distinct indices differ by at least 1. So when k = 0 the test i − last[x] ≤ 0 can never hold (the gap is always ≥ 1), and we correctly return false with no special-casing. Using ≤ rather than < matters: a gap of exactly k is a valid match per the spec, and < would miss the boundary case like [1,2,3,1], k = 3.

Why we don't need the value's full history. We never care about all the places x appeared — only the closest one behind us. That's why a single integer per value suffices and the map stays a flat value→index table rather than value→list-of-indices.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [1, 2, 3, 1, 2, 3], k = 2

Hash-map state

i=0, x=1

lookup 1

ValueIndex / state

1→ 0

Continue scanning

unseen → 1→0

Final resultfalse

C · Code with teaching comments

solution.javaJava

Hash Map of Last Index (Optimal, simplest) — optimal

3 teaching notes

1
public boolean containsNearbyDuplicate(int[] nums, int k) {
2
    Map<Integer, Integer> last = new HashMap<>();
3
    for (int i = 0; i < nums.length; i++) {
4
        // Most recent index of this value, or null if never seen.
5
        Integer prev = last.get(nums[i]);
6
        // Gap to the nearest prior occurrence; <= k (inclusive) is a match.
7
        if (prev != null && i - prev <= k) {
8
            return true;
9
        }
10
        // Always overwrite with the current index — nearest prior gives the smallest
11
        // future gap.
12
        last.put(nums[i], i);
13
    }
14
    return false;
15
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.15 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

The leap from Contains Duplicate is replacing the set ('seen ever?') with a map to the last position ('seen how recently?'). Recency, not mere existence, is the quantity the distance constraint demands — and the smallest gap always comes from the nearest prior occurrence, which is exactly why we overwrite.

ComplexityO(n) time, O(n) space — Single pass, O(1) average map operations per element → O(n) time. The map can hold up to n distinct values → O(n) space.

E · Edge cases and pitfalls7nums = [1], k = 1 — Single element, no pair possible → false.Explore edge cases

Edge cases handled

nums = [1], k = 1Single element, no pair possible → false.
nums = [1,1], k = 0Seen 1 at 0, gap 1 > 0 → false. k=0 never matches.
nums = [1,1], k = 1Gap 1 ≤ 1 → true.

Pitfalls

Keeping the first index instead of overwriting — misses closer later pairs.
Using < k instead of <= k — fails [1,2,3,1], k=3.
In Java, using last.containsKey then last.get is two lookups; one get with a null check is cleaner.
Assuming a small value range and indexing an array — values span ±10⁹.

03.2

Approach 2 of 2

Sliding Window — Set of the Last k Values

TimeO(n)SpaceO(min(n, k))

Bring up when the interviewer asks to bound memory: this caps space at O(min(n, k)) instead of O(n).

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Instead of remembering every value ever seen, only remember the values in the current window of the last k indices. If the incoming value is already in that window, it's a duplicate within distance k.

2Hint 2Explore hint

Maintain a set of the values at indices [i-k, i-1]. Before adding nums[i], check membership; after, evict nums[i-k] so the window never exceeds size k.

3Hint 3Explore hint

The set's size is bounded by k, so this trades the O(n) map for O(k) memory.

A · Core idea

This variant reframes the problem as a literal sliding window of width k over indices. We keep a hash set containing exactly the values currently inside the window [i − k, i − 1]. When we arrive at index i, the question 'is there an equal value within distance k behind me?' becomes simply 'is nums[i] already in the set?'.

Why the window size is exactly k. A pair (i, j) qualifies when |i − j| ≤ k. Looking backward from i, the eligible partners are at indices i − 1, i − 2, …, i − k — that's k positions. So the set must hold precisely those k values. Before processing i, if i > k we evict the value that has just fallen out of the window, nums[i − k], keeping the set size capped at k. This eviction is what bounds memory at O(k) rather than O(n).

Why a set, not a map. Within the window we don't need indices at all — membership is sufficient, because everything in the set is by construction within distance k. The window structure encodes the distance constraint positionally, so the value alone answers the question. That's the conceptual difference from approach 1: approach 1 stores positions and computes gaps; this one bakes the gap into which elements are present.

Why this matters when k is small relative to n. If n = 10⁵ but k = 10, the map approach still allocates up to 10⁵ entries, while the window holds at most 10. For memory-constrained or streaming scenarios — where you can only retain a recent buffer — the sliding window is the right tool. The trade-off is a touch more bookkeeping (the eviction step) and slightly worse constant factors from the extra remove operations.

Why eviction uses `nums[i − k]` and the guard `i ≥ k`. When i reaches k, index i − k = 0 is the one leaving the window of the next step, so we remove its value first. For i < k the window hasn't filled yet and there's nothing to evict — hence the guard. Getting this index off by one (i − k vs i − k − 1) is the classic bug; anchoring on 'the window covers the last k indices' keeps it straight.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [1, 2, 3, 1], k = 3

i=0, x=1

i>k? 0>3 no. 1 absent → add

Statewindow={1}

Final resulttrue

C · Code with teaching comments

Reference implementation previewpublic boolean containsNearbyDuplicate(int[] nums, int k) { Set<Integer> window = new HashSet<>(); for (int i = 0; i < nums.length; i++) { if (i > k) { window.remove(nums[i - k - 1]);Explore the full code

solution.javaJava

Sliding Window — Set of the Last k Values — reference

3 teaching notes

1
public boolean containsNearbyDuplicate(int[] nums, int k) {
2
    Set<Integer> window = new HashSet<>();
3
    for (int i = 0; i < nums.length; i++) {
4
        // Once the window is full, the element at i-k-1 has fallen outside distance k.
5
        if (i > k) {
6
            // Evict the value leaving the window so the set stays within the last k
7
            // indices.
8
            window.remove(nums[i - k - 1]);
9
        }
10
        // Set.add returns false if the value was already present — that's a duplicate
11
        // within k.
12
        if (!window.add(nums[i])) {
13
            return true;
14
        }
15
    }
16
    return false;
17
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.17 lines

D · Why it works and complexityO(n) timeO(min(n, k)) spaceOpen the invariant and proofExplore the proof

When a constraint is 'within the last k', a fixed-width sliding window literally is the constraint — membership in the window answers the question with no arithmetic. Choose this over the global map whenever memory must stay proportional to the window, not the whole stream.

ComplexityO(n) time, O(min(n, k)) space — Each element is added and removed from the set at most once → O(n) total set operations, each O(1) average. The set holds at most k elements → O(min(n, k)) space.

E · Edge cases and pitfalls6nums = [1,2,3,1,2,3], k = 2 — Window only ever holds 2 prior values; each repeat is distance 3 away and has been evicted → false.Explore edge cases

Edge cases handled

nums = [1,2,3,1,2,3], k = 2Window only ever holds 2 prior values; each repeat is distance 3 away and has been evicted → false.
nums = [1,1], k = 0i=1 > k=0 → evict nums[0]=1; window empty; 1 absent → false. k=0 correctly never matches.

Pitfalls

Evicting nums[i-k] instead of nums[i-k-1] — off-by-one shrinks the window too aggressively.
Evicting after the membership test in the wrong order so a still-valid partner gets removed early.
Using remove instead of discard in Python — KeyError when the value was already removed.
Forgetting the i > k guard — IndexOutOfBounds on early iterations.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic boolean containsNearbyDuplicate(int[] nums, int k) { Map<Integer, Integer> last = new HashMap<>(); for (int i = 0; i < nums.length; i++) { Integer prev = last.get(nums[i]); if (prev != null && i - prev <= k) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Keeping the first index instead of the most recent

On nums=[1,2,1,1], k=1 storing only the first index of 1 (=0) makes every later 1 compute a gap from 0, missing the adjacent 1's at indices 2 and 3. Always overwrite.

Explore the code comparison

Don't write this

last = {}
for i, x in enumerate(nums):
    if x in last and i - last[x] <= k:
        return True
    if x not in last:
        last[x] = i
return False

Write this instead

last = {}
for i, x in enumerate(nums):
    if x in last and i - last[x] <= k:
        return True
    last[x] = i
return False

Strict less-than on the distance

The spec allows |i-j| == k. Using < k fails nums=[1,2,3,1], k=3 where the matching pair is exactly distance 3 apart.

Explore the code comparison

Don't write this

if (prev != null && i - prev < k) return true;

Write this instead

if (prev != null && i - prev <= k) return true;

Sliding-window eviction off-by-one

The element that leaves a width-k window at step i is at index i-k-1 (since the window covers i-1 down to i-k). Removing nums[i-k] evicts a still-valid partner one step early.

Explore the code comparison

Don't write this

if (i >= k) window.remove(nums[i - k]);

Write this instead

if (i > k) window.remove(nums[i - k - 1]);

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Hash map of last index, OR sliding-window set of size k

Code pattern to memorize

last = {}
for i, x in enumerate(nums):
    if x in last and i - last[x] <= k: return True
    last[x] = i   # always overwrite with the nearest index
return False

Rules to remember

1Always overwrite last[x] = i even on a non-match — the nearest previous index gives the smallest gap, the best chance of ≤ k.
2Compare i - last[x] <= k, not < k — distance exactly k is allowed.
3Edge case k == 0: no two distinct indices can be within distance 0, so the answer is always false (handle naturally, the gap is ≥ 1).
4Duplicate value alone is not enough — the indices must be close. This is Contains Duplicate plus a distance constraint.
5The sliding-window variant keeps a set of the last k elements; remove nums[i-k] as the window slides to cap space at O(k).

Use this pattern when

Find a repeated element within a bounded index/time window
'Have I seen this recently?' rather than 'ever?'
Stream/array problems with a 'within the last k' locality constraint
Near-duplicate detection where proximity matters

Choose another pattern when

Any duplicate anywhere counts → plain Contains Duplicate (a set, no distance)
Values must be close in VALUE too (|nums[i]-nums[j]| ≤ t) → Contains Duplicate III, needs buckets/TreeSet
Need the actual pair, not a boolean → store indices and return them
Window over a sum/length, not equality → different sliding-window template

Interview takeaway

Contains Duplicate II = Contains Duplicate + a distance constraint. Keep the most recent index of each value (overwrite always) and check the gap, or maintain a set of the last k values. The 'most recent index' insight — that overwriting beats keeping the first index — is the interview discriminator.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternHash map of last index (recency), or a fixed-width sliding-window set. Recognise it whenever 'duplicate' is qualified by 'within the last k' — proximity, not mere existence. The recency-overwrite insight and the window-eviction index are the two implementation discriminators.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Contains Duplicate
Drop the distance constraint — a single set answers 'any duplicate at all'.
Contains Duplicate III
Coming soon
Add a VALUE window |nums[i]-nums[j]| ≤ t on top of the index window — bucketing or a TreeSet over the last k elements.
Two Sum
Same value→index hash-map idea, but matching complements rather than equal values within a window.
Longest Substring Without Repeating Characters
Coming soon
Sliding window with last-seen indices to shrink on a repeat — a richer version of the window here.

Same pattern

←

Ransom Note

Continue · Next problem

Insert Delete GetRandom O(1)

easyArraysLC #219Frequently asked

Contains Duplicate II

LCPractice

Arrays & Hashing · 16 of 83 · 8 min

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

In plain English

Examples

Example 1

Input: nums = [1, 2, 3, 1], k = 3
Output: true
Note: The two 1's are at indices 0 and 3; |0 - 3| = 3 ≤ 3.

Example 2

Input: nums = [1, 0, 1, 1], k = 1
Output: true
Note: The 1's at indices 2 and 3 are distance 1 apart ≤ 1. (The 0/2 pair is too far, but the closest pair wins.)

Example 3

Input: nums = [1, 2, 3, 1, 2, 3], k = 2
Output: false
Note: Every repeated value is exactly distance 3 apart, which exceeds k = 2.

Example 4

Input: nums = [99, 99], k = 0
Output: false
Note: Distinct indices 0 and 1 have gap 1 > 0. k = 0 can never match.

Constraints

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

Clarifying questions4First question: Is the distance condition |i - j| <= k inclusive of k?Explore questions

Q1.Is the distance condition |i - j| <= k inclusive of k?
Yes, ≤ k. A gap of exactly k counts as a match. I'll use <= rather than <.
Q2.What happens when k is 0?
Two distinct indices have a gap of at least 1, which can never be ≤ 0, so the answer is always false. The code handles it naturally without a special case.
Q3.Can values be negative or very large?
Yes, up to ±10⁹, so I'll key the hash map by the integer value directly — no array-indexing tricks that assume a small non-negative range.
Q4.If k exceeds the array length, does it just become Contains Duplicate?
Effectively yes — every pair is within distance k, so any duplicate at all returns true. Both my solutions handle that without a branch.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you fold the index-distance constraint into a hash map cleanly — specifically whether you realize you should keep the MOST RECENT index of each value, not the first.

Where candidates slip

Storing the first occurrence index and never updating it, which can report a gap larger than k even when a closer pair exists; or using strict < k instead of <= k.

How to stand out

Offer both the value→last-index map and the fixed-size sliding-window set, explain the space trade-off, and connect it forward to Contains Duplicate III's value-window generalization.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Hash Map of Last Index (Optimal, simplest)Optimal	`O(n)`	`O(n)`	Lead with this — it's the cleanest. Stress 'I keep the MOST RECENT index of each value'.	Read
2	Sliding Window — Set of the Last k Values	`O(n)`	`O(min(n, k))`	Bring up when the interviewer asks to bound memory: this caps space at O(min(n, k)) instead of O(n).	Read

value → last index on [1,2,3,1], k=3nums = [1, 2, 3, 1], k = 3

How to read it:Each frame is the map after one step. The repeat of 1 finds last index 0; gap 3 ≤ 3 → true.

Frame 1
i=0, x=1
1 unseen → store 1→0
1→ 0
Frame 2
i=1, x=2
2 unseen → store 2→1
1→ 0
2→ 1
Frame 3
i=2, x=3
3 unseen → store 3→2
1→ 0
2→ 1
3→ 2
Frame 4
i=3, x=1
1 seen at 0, gap 3 ≤ 3 → return true
1→ 0
2→ 1
3→ 2
Match found.

Just inserted / updatedLooking upMatch

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2 · Optimal

Hash Map of Last Index (Optimal, simplest)

TimeO(n)SpaceO(n)

Lead with this — it's the cleanest. Stress 'I keep the MOST RECENT index of each value'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Plain Contains Duplicate uses a set: 'have I seen x before?'. Here you also need to know HOW LONG ago. What should the map's value be so you can answer that?

2Hint 2Explore hint

Map value → the last index where it appeared. When you re-see x, the gap is i − last[x]; if that's ≤ k you're done.

3Hint 3Explore hint

Crucially, always overwrite last[x] = i, even when the gap was too big — the nearest previous occurrence gives the smallest possible future gap.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [1, 2, 3, 1, 2, 3], k = 2

Hash-map state

i=0, x=1

lookup 1

ValueIndex / state

1→ 0

Continue scanning

unseen → 1→0

Final resultfalse

C · Code with teaching comments

solution.javaJava

Hash Map of Last Index (Optimal, simplest) — optimal

3 teaching notes

1
public boolean containsNearbyDuplicate(int[] nums, int k) {
2
    Map<Integer, Integer> last = new HashMap<>();
3
    for (int i = 0; i < nums.length; i++) {
4
        // Most recent index of this value, or null if never seen.
5
        Integer prev = last.get(nums[i]);
6
        // Gap to the nearest prior occurrence; <= k (inclusive) is a match.
7
        if (prev != null && i - prev <= k) {
8
            return true;
9
        }
10
        // Always overwrite with the current index — nearest prior gives the smallest
11
        // future gap.
12
        last.put(nums[i], i);
13
    }
14
    return false;
15
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.15 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(n) space — Single pass, O(1) average map operations per element → O(n) time. The map can hold up to n distinct values → O(n) space.

E · Edge cases and pitfalls7nums = [1], k = 1 — Single element, no pair possible → false.Explore edge cases

Edge cases handled

nums = [1], k = 1Single element, no pair possible → false.
nums = [1,1], k = 0Seen 1 at 0, gap 1 > 0 → false. k=0 never matches.
nums = [1,1], k = 1Gap 1 ≤ 1 → true.

Pitfalls

Keeping the first index instead of overwriting — misses closer later pairs.
Using < k instead of <= k — fails [1,2,3,1], k=3.
In Java, using last.containsKey then last.get is two lookups; one get with a null check is cleaner.
Assuming a small value range and indexing an array — values span ±10⁹.

03.2

Approach 2 of 2

Sliding Window — Set of the Last k Values

TimeO(n)SpaceO(min(n, k))

Bring up when the interviewer asks to bound memory: this caps space at O(min(n, k)) instead of O(n).

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

2Hint 2Explore hint

Maintain a set of the values at indices [i-k, i-1]. Before adding nums[i], check membership; after, evict nums[i-k] so the window never exceeds size k.

3Hint 3Explore hint

The set's size is bounded by k, so this trades the O(n) map for O(k) memory.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [1, 2, 3, 1], k = 3

i=0, x=1

i>k? 0>3 no. 1 absent → add

Statewindow={1}

Final resulttrue

C · Code with teaching comments

solution.javaJava

Sliding Window — Set of the Last k Values — reference

3 teaching notes

1
public boolean containsNearbyDuplicate(int[] nums, int k) {
2
    Set<Integer> window = new HashSet<>();
3
    for (int i = 0; i < nums.length; i++) {
4
        // Once the window is full, the element at i-k-1 has fallen outside distance k.
5
        if (i > k) {
6
            // Evict the value leaving the window so the set stays within the last k
7
            // indices.
8
            window.remove(nums[i - k - 1]);
9
        }
10
        // Set.add returns false if the value was already present — that's a duplicate
11
        // within k.
12
        if (!window.add(nums[i])) {
13
            return true;
14
        }
15
    }
16
    return false;
17
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.17 lines

D · Why it works and complexityO(n) timeO(min(n, k)) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6nums = [1,2,3,1,2,3], k = 2 — Window only ever holds 2 prior values; each repeat is distance 3 away and has been evicted → false.Explore edge cases

Edge cases handled

nums = [1,2,3,1,2,3], k = 2Window only ever holds 2 prior values; each repeat is distance 3 away and has been evicted → false.
nums = [1,1], k = 0i=1 > k=0 → evict nums[0]=1; window empty; 1 absent → false. k=0 correctly never matches.

Pitfalls

Evicting nums[i-k] instead of nums[i-k-1] — off-by-one shrinks the window too aggressively.
Evicting after the membership test in the wrong order so a still-valid partner gets removed early.
Using remove instead of discard in Python — KeyError when the value was already removed.
Forgetting the i > k guard — IndexOutOfBounds on early iterations.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Keeping the first index instead of the most recent

On nums=[1,2,1,1], k=1 storing only the first index of 1 (=0) makes every later 1 compute a gap from 0, missing the adjacent 1's at indices 2 and 3. Always overwrite.

Explore the code comparison

Don't write this

last = {}
for i, x in enumerate(nums):
    if x in last and i - last[x] <= k:
        return True
    if x not in last:
        last[x] = i
return False

Write this instead

last = {}
for i, x in enumerate(nums):
    if x in last and i - last[x] <= k:
        return True
    last[x] = i
return False

Strict less-than on the distance

The spec allows |i-j| == k. Using < k fails nums=[1,2,3,1], k=3 where the matching pair is exactly distance 3 apart.

Explore the code comparison

Don't write this

if (prev != null && i - prev < k) return true;

Write this instead

if (prev != null && i - prev <= k) return true;

Sliding-window eviction off-by-one

The element that leaves a width-k window at step i is at index i-k-1 (since the window covers i-1 down to i-k). Removing nums[i-k] evicts a still-valid partner one step early.

Explore the code comparison

Don't write this

if (i >= k) window.remove(nums[i - k]);

Write this instead

if (i > k) window.remove(nums[i - k - 1]);

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Hash map of last index, OR sliding-window set of size k

Code pattern to memorize

last = {}
for i, x in enumerate(nums):
    if x in last and i - last[x] <= k: return True
    last[x] = i   # always overwrite with the nearest index
return False

Rules to remember

1Always overwrite last[x] = i even on a non-match — the nearest previous index gives the smallest gap, the best chance of ≤ k.
2Compare i - last[x] <= k, not < k — distance exactly k is allowed.
3Edge case k == 0: no two distinct indices can be within distance 0, so the answer is always false (handle naturally, the gap is ≥ 1).
4Duplicate value alone is not enough — the indices must be close. This is Contains Duplicate plus a distance constraint.
5The sliding-window variant keeps a set of the last k elements; remove nums[i-k] as the window slides to cap space at O(k).

Use this pattern when

Find a repeated element within a bounded index/time window
'Have I seen this recently?' rather than 'ever?'
Stream/array problems with a 'within the last k' locality constraint
Near-duplicate detection where proximity matters

Choose another pattern when

Any duplicate anywhere counts → plain Contains Duplicate (a set, no distance)
Values must be close in VALUE too (|nums[i]-nums[j]| ≤ t) → Contains Duplicate III, needs buckets/TreeSet
Need the actual pair, not a boolean → store indices and return them
Window over a sum/length, not equality → different sliding-window template

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Contains Duplicate
Drop the distance constraint — a single set answers 'any duplicate at all'.
Contains Duplicate III
Coming soon
Add a VALUE window |nums[i]-nums[j]| ≤ t on top of the index window — bucketing or a TreeSet over the last k elements.
Two Sum
Same value→index hash-map idea, but matching complements rather than equal values within a window.
Longest Substring Without Repeating Characters
Coming soon
Sliding window with last-seen indices to shrink on a repeat — a richer version of the window here.

Same pattern

←

Ransom Note

Continue · Next problem

Insert Delete GetRandom O(1)