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 Twin Prism Bound.
Scanning the entire history after every event cannot keep up with live players.
How you win
- 1Recognize when Dual monotonic deques matches the clues
- 2Keep this true after every move: the two deque fronts are the exact maximum and minimum of the live window
- 3Reach the result within O(n)
Rules and pressure
- Target cost: O(n)
- State rule: the two deque fronts are the exact maximum and minimum of the live window
Lesson 1 of 3
Two rails order the same window differently. Their front-to-front distance is the complete validity test.
Your call · Maximum is 8, minimum is 2, and limit is 4. What next?