The maximum in every sliding window
A performance overlay showing the worst frame time in the last sixty frames, or a chart drawing a rolling peak, needs the maximum of a window that moves one step at a time. Recomputing the maximum for each window is O(n * k); a monotonic deque does the whole sweep in one pass.
Implement maxSlidingWindow(nums, k). nums is an array of numbers and k is the window size. Return an array holding the largest number in each window of k consecutive values, starting with the window at index 0 and moving one step right at a time, so the result has nums.length - k + 1 entries. Return an empty array when nums is empty, when k is less than 1, or when k is larger than the array.
Arguments
numsnumber[]- The input array of numbers.
knumber- The window size — how many consecutive values each maximum covers.
Returns
number[] — The largest number in each window of size k, left to right. [] when the window cannot fit.
Examples
maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3);
// [3, 3, 5, 5, 6, 7]maxSlidingWindow([4, 2, 12, 3], 1);
// [4, 2, 12, 3] — a window of 1 is just the inputmaxSlidingWindow([1, 2], 5);
// [] — window is larger than the arrayWhat it has to do
- Return one maximum per window, left to right.
- Return an empty array when
kis larger than the input, whenkis below 1, or when the input is empty. - Handle negative numbers and repeated values.
- Handle
kequal to 1 andkequal to the array length. - Make a single pass rather than scanning each window.
Notes
- A monotonic deque brings this down to O(n) total — each index is pushed and popped at most once — rather than the naive O(n * k).
- Store indices rather than values in the deque, so you can tell when the front has slid out of the window.
- Keep the deque's values strictly decreasing from front to back: before pushing a new index, drop every smaller value from the back — they can never be the max while this larger one is around.
Stuck? The javascript course covers everything this challenge needs.
- 1.reports the peak of each window
- 2.a window of one is the array itself
- 3.a window covering everything gives one answer
- 4.handles repeated and negative values
- 5.returns an empty array for impossible windows
These assertions run in your browser the moment you hit Run. Pass all of them to claim the XP.
Discussion
Sign in to postNo comments yet. Be the first to say something.