Sliding Window Maximum Hard 0 attempts
LeetCode ↗

Sliding Window Maximum

Hard HeapPriority Queue LeetCode

You're given an integer array nums and a window size k. A window of k consecutive elements slides across the array one step at a time, from the first position to the last. For each position of the window, record the maximum value inside it, and return these maximums as an array.

Input Format
Implement maxSlidingWindow(nums, k). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 ยท Run Sample

Input
nums = [1,3,-1,-3,5,3,6,7]
k = 3
Output
[3,3,5,5,6,7]

Example 2

Input
nums = [4,3,2]
k = 1
Output
[4,3,2]
Constraints
  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4
  • 1 <= k <= nums.length
Test Cases (2)
Case 1
Args: [[1,3,-1,-3,5,3,6,7],3] Expected: [3,3,5,5,6,7]
Case 2
Args: [[4,3,2],1] Expected: [4,3,2]
Topics
HeapPriority Queue

Monotonic Deque

Keep indices in decreasing value order. Remove expired indices from the front and smaller values from the back. A head index avoids shifting an array on every removal; periodic compaction keeps storage proportional to the window size.

javascript
function maxSlidingWindow(nums, k) {
  const deque = [], result = []; let head = 0;
  for (let i = 0; i < nums.length; i++) {
    while (head < deque.length && deque[head] <= i - k) head++;
    while (deque.length > head && nums[deque[deque.length-1]] <= nums[i]) deque.pop();
    deque.push(i);
    if (i >= k - 1) result.push(nums[deque[head]]);
    if (head >= k) { deque.splice(0,head); head = 0; }
  }
  return result;
}

Time: O(n) amortized | Space: O(k) auxiliary space, excluding output

Saved in this browser only. Private to you.

JavaScript