Contains Duplicate Within K Distance
- mosesg1123
- May 9
- 4 min read
Checking for nearby repeated events in a log or sensor stream is a common task in monitoring, fraud detection, and real‑time analytics. The “Contains Duplicate Within K Distance” problem forces you to manage temporal windows and fast membership checks efficiently.
Problem Statement
Given an integer array nums and an integer k, determine whether there are two distinct indices i and j in the array such that nums[i] == nums[j] and |i - j| <= k. Return true if such a pair exists, otherwise false.
Index: 0 1 2 3 4
Nums: [1, 2, 3, 1, 2]
↑
1 at index 3 matches 1 at index 0 (distance 3)
1. Clarify Requirements Before Jumping Into Code
Can k be zero or negative? Assume k > 0
Are array values arbitrary 32‑bit ints? Yes.
Array length bounds? Up to, say, 10⁵.
Should duplicates farther apart than k be ignored? Yes.
2. Identify the Category of the Question
This is a sliding‑window + hash problem. Common patterns:
Fixed‑size window maintenance
Hash‑set for fast membership
Hash‑map of most‑recent indices
Two‑pointer window contraction/expansion
3. Consider a Brute‑Force Approach to Understand the Problem
Brute‑force: for each index i, scan the next k positions j = i+1 … i+k and check if nums[i] == nums[j].
for i from 0 to n-1:
for j from i+1 to min(n-1, i+k):
if nums[i] == nums[j]: return true
return false
Time: O(n·k) which in worst case is O(n²).
Space: O(1)
This solution is too slow if both n and k are large.
4. Brainstorm More Solutions
Option 1:
The brute-force solution involves a lot of repeated work: I'm rescanning elements repeatedly to see if they are duplicates.
So to try and optimize, the first question I ask myself is: How can I quickly determine whether or not I've seen a particular element within K steps?
Hash Sets and Maps shine when it comes to constant look up time of elements! So how about I start with a hash set to track the last k elements that I've seen.
That naturally leads to a second question: How do I clean up the hash set to ensure that I am only tracking the last K elements?
This is sounding a lot like a sliding window! Every time I move forward one element in the array, I know exactly which element needs to drop from my hash set: nums[i-k].
Combining these two ideas:
Keep a hash‑set of up to k most recent values.
At index i:
If nums[i] in set → return true.
Add nums[i] to set.
If set size > k, remove nums[i-k].
Time: O(n), Space: O(k).
Option 2
Let's say I know there is at least one duplicate in the array. How would I know if they are within K elements? Easy, by comparing indices: i -j <= k
If I'm at element i, I have two of the three variables that I need. I'm just missing j, the index of the duplicate. How can I quickly identify the index of that element?
With a hash map!
I maintain a hash map where the key is the element from the array, and the value is the index of that element, then I can look up in constant time the index of j to calculate if it's within k distance!
But what if the same element appears 3 or more times in the array? I can just update the map entry for that element to ensure it's up-to-date with the most recent index for that element.
So to summarize this idea:
In my map lastIndex, store the pair {element, index}.
When I see num again at index i, check if i - lastIndex[element] <= k.
If yes, return true; otherwise update lastIndex[num] = i.
Time: O(n), Space: O(n).
Both solutions are equally valid and you are unlikely to be penalized for either decision. Option 2 does seem a bit cleaner than Option 1 though: one pass, one lookup, one update per element. It avoids explicitly managing the window size which should lead to slightly simpler code while enforcing the distance constraint. So that's the solution we'll choose for this post!
5. Discuss Trade‑Offs Between Your Solutions
Approach | Time | Space | Pros | Cons |
Brute‑force nested scan | O(n·k) | O(1) | Simple | Too slow when k or n is large |
Sliding‑window with hash‑set | O(n) | O(k) | Fast, bounded space | Needs explicit eviction logic |
Hash‑map of last indices | O(n) | O(n) | Simplest code, direct distance check | Slightly more space if many uniques |
6. Optimal Solution Recap
Maintain a hash‑map of { element, mostRecentIndex }. For each i, if element is in the hash-map with most recent index j, and i - j <= k, return true; otherwise update the mostRecentIndex for that element.
7. Write Pseudocode to Structure Your Thoughts
function containsNearbyDuplicate(nums, k):
map = empty hash‑map (value → last index)
for i from 0 to nums.length-1:
if nums[i] in map and i - map[nums[i]] <= k:
return true
map[nums[i]] = i
return false
8. Consider Edge Cases
Empty array or single element → return false.
k = 0 → never match two distinct indices → return false.
All distinct values → return false.
Immediate duplicate at distance = k → should return true.
Large k greater than array length → equivalent to checking any duplicate.
9. Write Full Code Syntax
import java.util.HashMap;
public class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
if (k <= 0) return false;
HashMap<Integer, Integer> lastIndex = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
Integer prev = lastIndex.get(nums[i]);
if (prev != null && i - prev <= k) {
return true;
}
lastIndex.put(nums[i], i);
}
return false;
}
}
10. Test Your Code
public static void main(String[] args) {
Solution sol = new Solution();
// no duplicates
System.out.println(sol.containsNearbyDuplicate(new int[]{1,2,3,4}, 2) == false);
// duplicate within k
System.out.println(sol.containsNearbyDuplicate(new int[]{1,2,3,1}, 3) == true);
// duplicate but too far apart
System.out.println(sol.containsNearbyDuplicate(new int[]{1,2,3,1}, 2) == false);
// k = 0
System.out.println(sol.containsNearbyDuplicate(new int[]{1,1}, 0) == false);
// multiple duplicates
System.out.println(sol.containsNearbyDuplicate(new int[]{1,0,1,1}, 1) == true);
}
11. Key Lessons to Remember for Future Questions
A hash‑map of value→index lets you enforce distance constraints in one pass.
Sliding‑window with a hash‑set is another pattern for “within k” problems, trading off eviction logic for simpler maps.
Always ask about edge cases like k=0, arrays of length ≤1, and large k values.
Breaking problems into “fast membership” and “distance check” clarifies your approach.
Writing clear pseudocode first prevents off‑by‑one errors in index arithmetic.
Good Luck and Happy Coding!
Comments