Pattern visualizer
Sliding Window Maximum (Two Pointers)
Two pointers l and r define the window: r advances one step at a time and l = r-k+1 trails k-1 behind, so l only enters valid range (>= 0) once the window has filled up. Recomputing the max across all k cells for every window is O(n*k) and wastes the overlap between adjacent windows. A deque of indices fixes that: before pushing r, pop every index at the back whose value is <= nums[r] — those are older AND smaller, so no window containing r can ever pick them. What survives is a front-to-back decreasing run, so the front is always the current window's maximum. The only other check is dropping the front once it falls behind l, since a value can still be the largest number seen without being inside the current window anymore. Animated on: nums = [1,3,-1,-3,5,3,6,7], k = 3 — report the maximum of every window of 3 consecutive numbers as it slides from left to right..
Two pointers bound the window, a monotonic deque tracks the max
nums=[1,3,-1,-3,5,3,6,7], k=3. Two pointers l and r bound the window; r sweeps right one step at a time while l = r-k+1 trails 2 behind. A deque of indices, kept strictly decreasing in value, means the front is always the max of whatever [l,r] currently covers.
1FUNCTION slidingWindowMax(nums, k)2 dq <- EMPTY LIST3 out <- EMPTY LIST4 FOR r <- 0 TO LENGTH(nums) - 15 l <- r - k + 16 WHILE dq NOT EMPTY AND nums[LAST(dq)] <= nums[r]7 REMOVE LAST FROM dq8 APPEND r TO dq9 IF FIRST(dq) < l10 REMOVE FIRST FROM dq11 IF l >= 012 APPEND nums[FIRST(dq)] TO out13 RETURN out
← / → step · space play · Home restart