A CDN ops board is given a per-minute 5xx series. For every start it wants the peak count inside the next k minutes — whether the spike is still the worst minute in the current frame. The first version nested a scan: for each start i, walk k cells, store the max. Two hundred minutes in staging returned in milliseconds. A month of per-minute ticks was still scanning when the dashboard timed out.

Sliding Window Maximum asks for the max of each contiguous window of length k. An array already gives nums[i] for free. Rescanning k cells per start uses that and still pays O(nk). A running sum can add-right and drop-left; a max cannot — the value that just aged out might have been the peak, and you have no second-best sitting around.

This is an interview writeup, not a window lecture. The sliding window post owns grow and shrink. The queue post owns two ends. Here we only care about a deque of useful indexes so the max is the front, not a restart of every frame.

The problem

Given an int[] nums and an int k, return an int[] answer of length n - k + 1 where answer[i] is the maximum among nums[i] … nums[i + k - 1]. The window slides one index at a time. k is at least 1 and at most n.

nums = [4, 2, 9, 1, 7, 3], k = 3  →  [9, 9, 9, 7]
nums = [8, 5, 3],          k = 1  →  [8, 5, 3]
nums = [2, 2, 2, 2],       k = 2  →  [2, 2, 2]

First row, left to right: [4, 2, 9] max 9, [2, 9, 1] max 9, [9, 1, 7] max 9, [1, 7, 3] max 7.

Note: k = 1 is the array itself. The window is contiguous — this is not “max of any k elements.”

Scan each window is the honest brute force

For every start, walk k cells and take the max. Correct. O(nk).

int[] maxSlidingWindowNested(int[] nums, int k) {
    int n = nums.length;
    int[] answer = new int[n - k + 1];
    for (int i = 0; i + k <= n; i++) {
        int max = nums[i];
        for (int j = 1; j < k; j++) {
            max = Math.max(max, nums[i + j]);
        }
        answer[i] = max;
    }
    return answer;
}

At n = 50 this is a rounding error. At a month of per-minute ticks you paid a nested scan for a question a deque answers because a smaller back can never beat the incoming value.

Decreasing deque of useful indexes

The deque holds indexes, not values. Values at those indexes decrease from front to back. The front is the current max. Walk left to right. Today is i.

  • While the deque is not empty and nums[i] is greater than nums[dq.peekLast()], pop the back. Those indexes lose to i in every window that still contains them.
  • Offer i at the back.
  • If the front index is <= i - k, it has left the window. Poll the front.
  • Once i >= k - 1, the window ending at i is complete: answer[i - k + 1] = nums[dq.peekFirst()].

Walk the first sample. Deque contents are indexes; the values are only for the comparison.

nums = [4, 2, 9, 1, 7, 3]   k = 3

i=0  4   []           offer 0                 [0]
i=1  2   4>2          offer 1                 [0, 1]
i=2  9   2<9 pop 1
         4<9 pop 0    offer 2   answer[0]=9   [2]
i=3  1   9>1          offer 3   answer[1]=9   [2, 3]
i=4  7   1<7 pop 3
         9>7          offer 4   answer[2]=9   [2, 4]
i=5  3   7>3          offer 5
         front 2 <= 2 poll 2    answer[3]=7   [4, 5]

answer = [9, 9, 9, 7]

Index 2 (9) sat at the front through three windows. Index 4 (7) became the front only after 9 aged out. That is the whole saving: smaller values behind a larger one never get a turn, and each index is offered and polled at most once.

The Java is that walk. ArrayDeque as a deque — both ends — storing indexes, not highs.

int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    int[] answer = new int[n - k + 1];
    Deque<Integer> dq = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i]) {
            dq.pollLast();
        }
        dq.offerLast(i);
        if (dq.peekFirst() <= i - k) {
            dq.pollFirst();
        }
        if (i >= k - 1) {
            answer[i - k + 1] = nums[dq.peekFirst()];
        }
    }
    return answer;
}

Time is O(n) — each index is offered once and polled at most once. Space is O(k) for the deque (a non-increasing window of length k is the worst case). Do not quote the nested O(nk) as the intended bill.

Note: Store indexes, not values. A deque of highs can tell you the max; it cannot tell you when that max aged out. Pop the back while it is smaller than the incoming value. Equals may stay, or you can pop <= so the later equal lives longer. Either is correct; the tighter deque is <=.

What interviewers usually poke next

  • Min of each window. Flip < to >. Same index deque, same age-out. Do not rewrite this method into that one.
  • Heap of (value, index). Correct, O(n log n), lazy-delete when the top is stale. Say why the deque is linear and the heap is not.
  • Return the index of each max, not the value. The front already is that index. The payload is dq.peekFirst(), not nums[...].
  • Streaming / online. Same deque; you do not need the whole array in memory if you emit as the right edge advances. The sliding window post still owns grow and shrink — do not re-lecture it.
  • k = 1 / k = n. One-cell windows copy the array. One window of length n is a single max. Both fall out of the same loop.

You are done with this problem when you can walk [4, 2, 9, 1, 7, 3] out loud, keep 9 at the front through three frames, pop it when it ages out, and say why a deque of values cannot expire the peak.