Understanding the Problem

We need to determine whether any value appears at least twice within a window of size k. Put differently, for any element at index i, we want to know if the same value appeared at any index j where i - k <= j < i.

The original Contains Duplicate problem just asks "are there duplicates anywhere?" This version adds a proximity constraint. That constraint is what makes the problem interesting, because it means we don't need to remember every element we've ever seen. We only need to remember what's in the current window.

Key Constraints:

1 <= nums.length <= 10^5 → With n up to 100,000, O(n^2) brute force might be too slow in the worst case, but O(n * min(n, k)) could pass depending on k. We should aim for O(n).
-10^9 <= nums[i] <= 10^9 → Values range widely, so using values as array indices isn't feasible. We need a hash-based approach.
0 <= k <= 10^5 → k can be as large as the array itself, so in the worst case the window is the entire array.

Approach 1: Brute Force

Intuition

The most direct approach: for each element, look backward at the previous k elements and check if any of them match. If we find a match, we're done. If we scan the entire array without finding one, we return false.

This is exactly what the problem is asking, translated almost word-for-word into code. For each index i, we check all indices j from max(0, i - k) to i - 1.

Algorithm

Iterate through each index i from 0 to n - 1
For each i, iterate backward through indices j from i - 1 down to max(0, i - k)
If nums[i] == nums[j], return true
If no duplicate pair is found after checking all elements, return false

Example Walkthrough

1Initialize: i=0, no previous elements to check

1/6

Code

Complexity Analysis

Time Complexity: O(n * min(n, k)). For each of the n elements, we check up to min(n, k) previous elements. When k is small, this is fast. When k approaches n, it degrades to O(n^2).
Space Complexity: O(1). We only use a few variables for loop indices. No additional data structures needed.

For each element, we're scanning up to k previous elements to find a match. What if we stored each value's most recent index so we could check in O(1) whether we've seen it recently enough?

Approach 2: Hash Map (Last Seen Index)

Intuition

Instead of looking backward from each element, we can flip the perspective. As we scan forward through the array, we keep a hash map that records the most recent index where each value appeared. When we encounter a value that's already in the map, we check whether the stored index is within distance k of the current index.

The key insight is that we only need the most recent index. If a value appeared at indices 2, 7, and 15, and we're currently at index 17 with k = 3, we only need to check against index 15. If index 15 isn't close enough, indices 2 and 7 certainly won't be either.

Why does this work?

We only need to compare against the most recent occurrence of a value. If the most recent occurrence is too far away, any earlier occurrence will be even farther. By updating the map with the current index every time, we ensure we're always checking the tightest possible distance.

Algorithm

Create a hash map to store each value's most recent index
Iterate through the array with index i
If nums[i] is already in the map and i - map.get(nums[i]) <= k, return true
Update the map with nums[i] -> i (overwriting any previous index)
If we finish the loop without finding a match, return false

Example Walkthrough

1Initialize: map = {}, k = 2

1/7

Code

Complexity Analysis

Time Complexity: O(n). We iterate through the array once. Each hash map lookup and insertion is O(1) on average.
Space Complexity: O(n). In the worst case (all unique elements), the map stores every element in the array.

The hash map approach is already O(n) time, but the map can grow to hold all n elements even though we only care about elements within distance k. What if we limited our data structure to only hold the k most recent elements?

Approach 3: Sliding Window with Hash Set

Intuition

Here's the idea: maintain a hash set that contains exactly the elements in a window of size k. As we move through the array, we add the current element to the set. If it's already there, we found a nearby duplicate. If the set grows beyond size k, we remove the oldest element (the one that just fell out of the window).

This is a classic sliding window pattern. The window represents the "neighborhood" of size k around the current index, and the set gives us O(1) membership checks within that window.

Algorithm

Create an empty hash set
Iterate through the array with index i
If nums[i] is already in the set, return true (duplicate within window)
Add nums[i] to the set
If the set size exceeds k, remove nums[i - k] (the element leaving the window)
If we finish without finding a duplicate, return false

Example Walkthrough

1Initialize: set = {}, k = 1

1/5

Code

Complexity Analysis

Time Complexity: O(n). We iterate through the array once. Each set operation (contains, add, remove) is O(1) on average.
Space Complexity: O(min(n, k)). The set never holds more than k + 1 elements. If k >= n, the set holds at most n elements.

Contains Duplicate II

Understanding the Problem

Key Constraints:

Approach 1: Brute Force

Intuition

Algorithm

Example Walkthrough

Code

Approach 2: Hash Map (Last Seen Index)

Intuition

Algorithm

Example Walkthrough

Code

Approach 3: Sliding Window with Hash Set

Intuition

Algorithm

Example Walkthrough

Code

Get Premium