One Locked Arena
Longest interval with endpoints in an array and at most one missing integer
An online game's arena ladder assigns an integer ID to every arena. Your activity log, cleared, contains the IDs of arenas you have cleared. An arena may appear more than once in the log, and the entries are not necessarily sorted.
You want to display a single ladder block from arena start through arena end, inclusive. A block is eligible when:
- Both endpoint arenas have been cleared.
- At most one integer ID inside the block has not been cleared. That arena can be displayed as locked.
The length of a block is end - start + 1, including a locked arena if there is one.
Return [start, end] for the eligible block with the greatest length. If several blocks have that length, choose the one with the smallest start. Return an empty list if the activity log is empty.
Repeated entries do not change whether an arena has been cleared.
Examples
Example 1
Input: cleared = [11,8,7,10,14,10] Output: [7,11]
Arenas 7, 8, 10, and 11 form a block with only arena 9 locked. Arena 14 is too far away to extend that block without introducing another missing arena. The repeated entry for arena 10 has no effect.
Example 2
Input: cleared = [-4,-3,-1,0,3,4,6,7] Output: [-4,0]
The block from -4 through 0 and the block from 3 through 7 have equal lengths and each contains one locked arena. The tie is resolved by choosing the block with the smaller starting ID.
Example 3
Input: cleared = [] Output: []
An empty activity log cannot supply cleared endpoints, so no block can be displayed.
Constraints
- 0 <= cleared.length <= 7000
- -10^9 <= cleared[i] <= 10^9
- Arena IDs are integers; negative IDs are valid.
The intended solution takes expected O(n) time and O(n) extra space using hash-based collections, where n is the length of the activity log.
Hints
Show hint 1Hint 1
Ignore repeated IDs. Which cleared IDs can be the beginning of a maximal run of consecutive cleared arenas?
Show hint 2Hint 2
An eligible block either lies within one consecutive run or joins two runs with exactly one missing ID between them.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you return every maximum-length eligible block, ordered by starting ID?
- How would you change the solution to allow up to k missing arena IDs, while still requiring cleared endpoints?
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