Pattern visualizer
Sliding Window Maximum
The obvious loop re-reads all k cells for every window, which is O(n·k) and repeats work the previous window already did. A deque of indices fixes that with one rule: before pushing i, pop every index at the back whose value is <= nums[i]. Those are older AND smaller, so no future window can ever pick them over i. What is left is a front-to-back decreasing run, and the front is the window's maximum for free. One more check per step — drop the front if it has slid out of range — keeps the deque honest about which window it is describing. Animated on: nums = [5,3,4,1,2,6], k = 3 — report the maximum of every window of 3 consecutive numbers..
Monotonic deque — the front is always the answer
nums=[5,3,4,1,2,6], k=3. Re-scanning all 3 cells per window would be O(n·k). Instead keep a deque of INDICES whose values fall from front to back — then the front is always the current window's maximum, and every element is pushed and popped at most once.
1FUNCTION maxSlidingWindow(nums, k):2 dq <- empty deque of indices3 out <- empty list4 FOR i <- 0 TO LENGTH(nums) - 1:5 IF dq NOT EMPTY AND FRONT(dq) <= i - k:6 REMOVE FRONT(dq)7 WHILE dq NOT EMPTY AND nums[BACK(dq)] <= nums[i]:8 REMOVE BACK(dq)9 APPEND i TO dq10 IF i >= k - 1:11 APPEND nums[FRONT(dq)] TO out12 RETURN out
← / → step · space play · Home restart