Shortest stretch, same degree
The shortest stretch holding every copy of the most frequent value. About 12 minutes.
No label this time
Mastery problems mix ideas from this topic without saying which. A good way in: ask what you'd need to remember about each value as you walk past it. How many times you've seen it? Where you first saw it? Where you saw it last?
Write those facts down as a short list, then pick a map for each one. The answer is often just a little arithmetic on top.
- 1
- count 1, 0..0
- 2
- count 2, 1..2
Walk once and remember three things per value: how many, where it first appeared, where it last appeared.
In [1, 2, 2, 3, 1], what is the shortest stretch holding every copy of 2?
- ALength 2
- BLength 5
- CLength 1
Show the answer
Length 2. Both 2s sit at positions 1 and 2.
Shortest stretch, same degree
The degree of a list is the highest number of times any value appears. Return the length of the shortest run of consecutive numbers that has the same degree as the whole (non-empty) list.
nums = [1, 2, 2, 3, 1, 4, 2] → 6
1 ≤ n ≤ 500,000