Problem context and objectives
Mission briefing
Live-ops game engineer · A multiplayer arena is reporting bursts of lag
Find the smallest or strongest contiguous time window: The Descending Prism.
Scanning the entire history after every event cannot keep up with live players.
How you win
- 1Recognize when Monotonic deque maximum matches the clues
- 2Keep this true after every move: deque values decrease from front to back and every index lies in the window
- 3Reach the result within O(n)
Rules and pressure
- Target cost: O(n)
- State rule: deque values decrease from front to back and every index lies in the window
Lesson 1 of 3
Remove expired candidates from the front and defeated candidates from the back. Watch the two operations separately.
Your call · Before 5 arrives at index 4, candidates are [1:3, 2:-1, 3:-3]. With k=3, what leaves first?