What pattern does Contains Duplicate II use?

The Pattern: Hash Maps (Index Tracking for Duplicate Detection) The Heuristic: When needing to detect duplicates within a fixed index distance, use a hash map to remember the last occurrence of each element and check the distance on-the-fly to achieve O(n) time.

Contains Duplicate II — Hash Maps

Q: How do you solve Contains Duplicate II?

Iterate through nums once, maintaining a hash map from number to its last seen index. For each number, if it exists in the map and the index difference is at most k, return true immediately. Otherwise, update the map with the current index. If no such pair is found, return false after the loop.

Q: What is the time complexity of Contains Duplicate II?

O(n). Each element is processed once, and hash map lookups and updates are O(1) on average, resulting in linear time complexity.

Problem

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.

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

Example

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

Output: true

The algorithm scans the array while tracking the last seen index of each number. At index 0, number 1 is stored with index 0. At index 3, the number 1 appears again. The difference between indices 3 and 0 is 3, which is within the allowed distance k=3, so the function returns true immediately. This early detection avoids unnecessary scanning of the entire array.

Approach

Straightforward Solution

A naive approach would compare every pair of elements within distance k, resulting in O(n*k) time complexity, which is too slow for large inputs.

Core Observation

The problem requires detecting duplicates within a sliding window of size k. The key is to efficiently track the most recent occurrence of each number and check if the current occurrence is close enough to the previous one.

Path to Optimal

Preview

The insight is to use a hash map to store the last index where each number appeared. As we iterate through nums, for each number, we check if it has been seen before and if the difference between the current index and the stored index is at most k…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Iterate through nums once, maintaining a hash map from number to its last seen index. For each number, if it exists in the map and the index difference is at most k, return true immediately…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

Each element is processed once, and hash map lookups and updates are O(1) on average, resulting in linear time complexity.

Space

O(n)

In the worst case, all elements are distinct and stored in the hash map, requiring space proportional to the input size.

Solution

Python

1class Solution:
2    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
3
4        last_seen = {}
5
6        for i, n in enumerate(nums):
7
8            if n in last_seen and i - last_seen[n] <= k:
9                return True
10
11            last_seen[n] = i
12
13        return False

Step-by-Step Solution

1

Track Last Seen Indices of Numbers Using a Hash Map

4	`last_seen = {}`

Objective

To maintain a mapping from each number to its most recent index in the array.

Key Insight

By storing the last seen index of each number, the algorithm can instantly check if a newly encountered duplicate is within the allowed distance k. This transforms the problem from a costly pairwise comparison to a constant-time lookup per element, enabling a single-pass O(n) solution.

Interview Quick-Check

Core Logic

The hash map stores numbers as keys and their last seen indices as values, enabling O(1) average-time distance checks.

Common Pitfalls & Bugs

Failing to update the last seen index after checking can cause incorrect results by using stale indices.

2

Iterate Through Array and Detect Nearby Duplicates

To scan the array, checking for duplicates within distance k and returning true immediately upon detection.

3

Update the Last Seen Index

Record the current index of the number for future comparisons.

4

Return False When No Nearby Duplicates Are Found

To conclude the function by returning false if no duplicates within distance k are detected after full iteration.

3 more steps with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 8 Critical

if n in last_seen and i - last_seen[n] <= k:

Check if the current number has been seen before and if the index difference is within k.

This conditional is the core correctness check that ensures duplicates are only considered if they are close enough, directly implementing the problem's requirement.

Line 11 Critical

last_seen[n] = i

Update the last seen index of the current number.

Updating the index ensures that the hash map always reflects the most recent occurrence, which is critical for accurate distance checks in subsequent iterations.

Full line-by-line criticality + rationale for all 6 lines available on Pro.

Test Your Understanding

Why is it necessary to check the index difference before returning true when a duplicate is found?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Contains Duplicate II from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Contains Duplicate II drill

or drill a free problem

1	`class Solution:`
2	`def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:`
3
4	`last_seen = {}`
5
6	`for i, n in enumerate(nums):`
7
8	`if n in last_seen and i - last_seen[n] <= k:`
9	`return True`
10
11	`last_seen[n] = i`
12
13	`return False`