289. A Repeat Close By
Core1000 ms256 MBSolved by 0%
Print Yes if the array contains two equal values at positions at most k
apart, and No otherwise.
1 2 3 1 with k = 3 -> Yes (positions 0 and 3)
1 2 3 1 with k = 2 -> No (they are 3 apart)
A set of seen values is not enough, because it forgets WHERE each was seen. Keep a map from value to its most recent position instead.
The most recent position is the right one to keep. An earlier occurrence of the same value is always further away, so it can never help.
Constraints - `1 ≤ n ≤ 200000` - `0 ≤ k ≤ 200000` - `-1000000000 ≤ a[i] ≤ 1000000000`
Input
The first line contains two integers n and k.
The second line contains n integers.
Output
Print Yes or No on one line.
Input4 3
1 2 3 1
OutputYes
Notehas a repeat exactly k apart, which counts
Input4 2
1 2 3 1
OutputNo
Noteis the same array with the repeat one step too far
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.
Hint 1Where to start
Hint 2The approachOpen hint 1 first. This one carries on from it.
Hint 3PseudocodeOpen hint 2 first. This one carries on from it.
Hint 4Full solutionOpen hint 3 first. This one carries on from it.