Chess Club Review Reel
Endpoints of the shortest subarray meeting all per-value quotas
A chess club records its members' puzzle attempts in chronological order. Each entry in attempts is the integer ID of the member who made that attempt.
The coach wants to extract one uninterrupted section of this log for a review reel. For each index i, the reel must contain at least quotas[i] attempts by member members[i]. Attempts by other members may appear in the reel and still contribute to its length.
Return the inclusive, zero-based endpoints [start, end] of the shortest section that meets every quota. If several sections have the same minimum length, return the one with the smallest start.
Return [-1, -1] if no section meets every quota. Member IDs are labels; their numerical values have no other significance.
Examples
Example 1
Input: attempts = [4,2,4,9,4,2], members = [4,9], quotas = [2,1] Output: [2,4]
The section from index 2 through index 4 contains two attempts by member 4 and one by member 9. No shorter section can contain all three required attempts.
Example 2
Input: attempts = [3,8,3,8], members = [3,8], quotas = [1,1] Output: [0,1]
The sections from index 0 through index 1 and from index 1 through index 2 both meet the quotas with minimum length. Choose the former because its starting index is smaller.
Example 3
Input: attempts = [7,2,2,5], members = [7], quotas = [2] Output: [-1,-1]
Member 7 appears only once in the entire log, so the quota of two attempts cannot be met.
Constraints
- 0 <= attempts.length <= 10000
- 1 <= members.length <= 1000
- quotas.length == members.length
- All IDs in members are distinct.
- -10^9 <= attempts[i], members[i] <= 10^9
- 1 <= quotas[i] <= 10000
The intended solution runs in O(n + m) time and O(m) auxiliary space, where n is the number of attempts and m is the number of requested members.
Hints
Show hint 1Hint 1
Track counts only for requested members, along with the total number of required occurrences that are still missing.
Show hint 2Hint 2
Once a window meets every quota, move its left endpoint rightward while recording valid candidates. Stop shrinking when a required occurrence becomes missing.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you return the number of sections that meet every quota instead of the shortest section?
- If each attempt had a positive duration, how would you minimize total reel duration rather than the number of entries?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem