Skip to content

Peak of Every Window

Jump to bottom
Andrew Burke edited this page Aug 19, 2026 · 1 revision

TIP103 Unit 12 Session 2 (Click for link to problem statements)

Peak of Every Window

A live dashboard slides a window of width k across the readings in nums, one step at a time. For each window position it needs the maximum reading currently visible.

Return a list of the maximums for every window position.

def max_sliding_window(nums, k):
    pass

Problem Highlights

  • 💡 Difficulty: Hard
  • ⏰ Time to complete: 30-40 mins
  • 🛠️ Topics: Sliding Window, Monotonic Deque, Queues

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?

  • Q: How many window positions are there for a list of length n and a window of width k?

    • A: There are n - k + 1 positions, since the window slides one step at a time from the start of nums until its right edge reaches the last reading. The output list has exactly that many maximums.

  • Q: Can the readings be negative, and can values repeat?

    • A: Yes. Readings may be negative or duplicated; the window maximum is simply the largest value currently visible, ties included.

  • Q: Do we need each maximum's position, or just its value?

    • A: Just the value. For each window position we append the maximum reading to the result list, in order.
HAPPY CASE
Input: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
Output: [3, 3, 5, 5, 6, 7]
Explanation: The windows are [1,3,-1], [3,-1,-3], [-1,-3,5], [-3,5,3], [5,3,6], and [3,6,7]. Their maximums are 3, 3, 5, 5, 6, and 7.

EDGE CASE
Input: nums = [4, -2], k = 1
Output: [4, -2]
Explanation: With a window of width 1, every reading is its own maximum.

Input: nums = [9, 8, 7, 6], k = 4
Output: [9]
Explanation: The window covers the entire list, so there is only one position and one maximum.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Sliding Window Maximum Problems, we can consider the following approaches:

  • Brute Force: Recompute max() over each window; simple but repeats work, costing O(N * K).
  • Monotonic Deque: Maintain a double-ended queue of indices whose values decrease from front to back, so the front is always the current window's maximum. Each index enters and leaves the deque at most once, giving O(N) overall.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Slide across nums once, keeping a deque of indices. Before adding a new reading, evict indices that have fallen out of the window on the left, and evict indices of smaller readings from the right, since they can never be a future maximum while the new reading is in the window. The value at the front of the deque is then the maximum of the current window.

1) Initialize an empty result list and an empty deque of indices.
2) For each index i and reading num in nums:
   a) Pop indices from the front of the deque while they are outside the window (index <= i - k).
   b) Pop indices from the back of the deque while their readings are smaller than num.
   c) Append i to the back of the deque.
   d) If i >= k - 1 (the first full window has formed), append nums[front of deque] to the result.
3) Return the result list.

⚠️ Common Mistakes

  • Storing values instead of indices in the deque, which makes it impossible to tell when the front element has slid out of the window.
  • Using the wrong eviction boundary (e.g. window[0] < i - k instead of window[0] <= i - k), leaving a stale index in the window one step too long.
  • Appending to the result before the first full window has formed, producing n outputs instead of n - k + 1.
  • Popping equal values with <= instead of < is still correct here, but popping larger values from the back breaks the decreasing invariant entirely.

4: I-mplement

Implement the code to solve the algorithm.

from collections import deque

def max_sliding_window(nums, k):
    result = []
    window = deque()  # stores indices; readings decrease from front to back

    for i, num in enumerate(nums):
        # Remove indices that have slid out of the window
        while window and window[0] <= i - k:
            window.popleft()
        # Remove indices whose readings are smaller than the incoming one
        while window and nums[window[-1]] < num:
            window.pop()
        window.append(i)
        # Record the max once the first full window has formed
        if i >= k - 1:
            result.append(nums[window[0]])

    return result

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

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

    • i=0 (1): deque holds [0]. Window not full yet.
    • i=1 (3): 3 evicts index 0 (value 1); deque = [1]. Window not full yet.
    • i=2 (-1): deque = [1, 2]. First full window; front is index 1 → append 3.
    • i=3 (-3): deque = [1, 2, 3]. Front index 1 still in window → append 3.
    • i=4 (5): index 1 slides out; 5 evicts indices 3 and 2; deque = [4] → append 5.
    • i=5 (3): deque = [4, 5]. Front index 4 → append 5.
    • i=6 (6): 6 evicts indices 5 and 4; deque = [6] → append 6.
    • i=7 (7): 7 evicts index 6; deque = [7] → append 7.
    • Output: [3, 3, 5, 5, 6, 7] ✓

  • Input: nums = [4, -2], k = 1

    • Each reading forms its own window. Output: [4, -2] ✓

  • Input: nums = [9, 8, 7, 6], k = 4

    • The deque keeps [0, 1, 2, 3] (already decreasing); the only full window reports nums[0]. Output: [9] ✓

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the number of readings in nums and K is the window width.

  • Time Complexity: O(N) because each index is appended to the deque once and removed at most once, so all deque operations amortize to constant time per reading. This beats the O(N * K) brute force.
  • Space Complexity: O(K) for the deque, which never holds more than one window's worth of indices (plus O(N - K + 1) for the output list itself).

Clone this wiki locally