Remember the latest position
Keep the last position of every value to spot close repeats. About 8 minutes.
This time, remember the latest sighting
Now the question flips: does any number repeat close together, within k boxes? Like a shop's fraud check asking whether the same card was used twice within a few minutes.
To find a close repeat, the copy that matters is the most recent one. So the log should hold the last place you saw each number, and you update it every time you see it again.
1 is new: last seen in box 0.
Check, then update
At each box, look up the number in the log. If it's there and the gap is k or less, you've found a close repeat. If not, no earlier copy can be closer, so write down this box as the latest sighting and move on.
Do the check before the update. Update first and you'd be comparing the box with itself: a gap of 0, every time.
last = {}
for j, x in enumerate(nums):
if x in last and j - last[x] <= k:
return True
last[x] = j
return Falsek is 1, and the numbers are 4, 9, 4, 4. At which box is a close repeat first found?
- ABox 3
- BBox 2
- CNever
Show the answer
Box 3. At box 3, the latest 4 was in box 2, just 1 away.
Nearby repeat
You get a list of numbers and a distance k. Return true if two positions i < j hold the same value and j − i is at most k. Otherwise return false.
nums = [1, 2, 3, 1], k = 3 → true
0 ≤ n ≤ 1,000,000 · 0 ≤ k ≤ n