Sliding Window Maximum

Difficulty: Hard

Problem

Given an integer array nums and a window width k, imagine a frame that starts at the far left of the array and slides one step to the right at a time until it reaches the end. Only the k values inside the frame are visible at any moment. For every frame position, record the largest visible value, and return all of these maxima in order.

Example

Input: nums = [4, 2, 12, 3, 8, 1, 7], k = 3
Output: [12, 12, 12, 8, 8]
Explanation: The frames [4,2,12], [2,12,3], [12,3,8], [3,8,1], [8,1,7] have maxima 12, 12, 12, 8 and 8.

Brute-force approach

For each window of size k, scan all k elements to find the maximum.

Steps

  1. For each window position i (0 to n-k)
  2. Scan elements from i to i+k-1
  3. Find the maximum in the window
  4. Add maximum to result

Time complexity: O(n * k) · Space complexity: O(n - k + 1)

Trade-offs

  • Scans k elements per window: 18 comparisons for just 8 elements!
  • Adjacent windows overlap by k-1 elements, we re-compare them every time
  • What if we kept a 'shortlist' of max candidates that we update incrementally?

Optimal approach

Key insight: Maintain a deque of indices in decreasing order of their values. The front of the deque is always the maximum. Remove from back when a larger element arrives, remove from front when it leaves the window.

Use a monotonic decreasing deque. The front always holds the index of the current window's maximum.

Steps

  1. For each index i in nums
  2. Remove expired front indices (outside window)
  3. Remove back indices with value ≤ nums[i]
  4. Push i to deque
  5. If i ≥ k-1, record nums[deque.front] as window max

Time complexity: O(n) · Space complexity: O(k)

Pseudocode

function maxSlidingWindow(nums, k):
    deque = []   // stores indices
    result = []
    
    for i from 0 to len(nums):
        // Remove indices outside window
        while deque not empty and deque[0] <= i - k:
            deque.removeFirst()
        // Remove smaller elements from back
        while deque not empty and nums[deque.last] <= nums[i]:
            deque.removeLast()
        deque.append(i)
        if i >= k - 1:
            result.append(nums[deque[0]])
    return result

Hints

  • The deque front always holds the index of the maximum in the current window
  • We remove elements from the back that are smaller than the current element
  • We remove elements from the front that are outside the window

Complexity questions

Time complexity of scanning each window?

O(n * k). n-k+1 windows × k elements each = O(n*k).

Why is the monotonic deque approach O(n)?

Each element is added and removed at most once from the deque. n additions + at most n removals = O(2n) = O(n) amortized.

Space complexity of the deque approach (excluding output)?

O(k). The deque contains at most k indices (window size).

Check your understanding of Sliding Window Maximum

For [1,3,-1,-3,5,3,6,7] with k=3, what is the max of the first window [1,3,-1]?

3. max(1, 3, -1) = 3.

For [1,3,-1,-3,5,3,6,7] with k=3, what is the full output array?

[3, 3, 5, 5, 6, 7]. Windows: [1,3,-1]→3, [3,-1,-3]→3, [-1,-3,5]→5, [-3,5,3]→5, [5,3,6]→6, [3,6,7]→7.

How many values does the output array contain for an array of length n with window size k?

n - k + 1. The window can start at indices 0 through n-k, giving n-k+1 positions.

Related problems

Keep practising