Sliding Window Maximum

Difficulty: Hard

Problem

You are given an array of integers nums and an integer k. There is a sliding window of size k which moves from the very left to the very right. You can only see k numbers in the window. Each time the window moves right by one position. Return the max sliding window.

Example

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

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)