DSA sheet · Arrays · Sliding window pattern (fixed size + monotonic deque)

Sliding Window Maximum

The window here has a fixed size k, so sliding it is easy. The hard part is knowing the maximum of the window after every slide. A sum is easy to update (add the new item, subtract the old one), but a maximum isn't: when the biggest item leaves, you don't know who's next. The teacher goes from the two-loop brute force, to the idea of a heap, to the best answer, a monotonic deque that always keeps the current maximum at its front.

The deque trick (throw away items that can never be the answer again) is the same idea as the monotonic stack. It's worth learning properly, because it comes back in many "max/min of every window" problems.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Sliding window and deques from scratch
• Part A · Brute force: max of every window with two loops
• Part B · Why a plain slide fails, and the heap idea
• Part C · Optimal: the monotonic deque
• Part D · Revision page

Part 0 · Before starting

Subarray and window

A subarray is a continuous piece of the array (no gaps). A window is a subarray we look at through two indexes, left and right, both included. Its length is right − left + 1.

The brute-force way to visit windows is two loops: one for the start, one walking over the items of that window. Neighbouring windows share almost all their items, so the inner loop keeps re-reading the same numbers. A sliding window moves step by step and only handles what changes: one item comes in on the right, one item leaves on the left.

Fixed vs variable windows

A variable window needs a monotonic rule (if a window is valid, every smaller window inside it is valid too). That's why it fails for sums with negative numbers. A fixed window doesn't need this: its size never changes, we just slide it.

For a fixed window of size k over n items, the windows start at 0, 1, …, n − k. So there are n − k + 1 windows, and that's the length of the answer list.

Which optimisation pattern? (the teacher's 4-pattern check)

The problem literally says "a window of size k moving from left to right" → fixed sliding window. The question is only how to get each window's max quickly.

What is a deque?

A deque ("deck", double-ended queue) is a line of items where you can add or remove at both ends, each in O(1).

A plain Python list is O(n) for removing from the front, so always use deque here.

What is a monotonic deque?

Monotonic = always going one way. In this problem the deque keeps indexes whose values are decreasing from front to back. Before adding a new item at the back, we pop every item at the back that is smaller than it. Result: the front is always the biggest value of the current window. Part C proves why the popped items are never needed again.

Part A · Brute force: max of every window with two loops

LeetCode 239 · Hard

1The question in simple words

You get an array nums and a window size k. Put the window on the first k items, then slide it one step to the right at a time until it hits the end. For every position of the window, write down the biggest number inside it. Return that list.

Answer: [3, 3, 5, 5, 6, 7]. The input has 8 items but the answer only has 6.

Why n − k + 1 answers? (the teacher derives it)

The very first answer appears only once the window is full, at index k − 1. The first k − 1 items can't produce an answer on their own. After that, every new item gives exactly one answer. So the answer length is n − (k − 1) = n − k + 1. Here 8 − 3 + 1 = 6 ✓. (Opening the bracket: −(k − 1) = −k + 1.)

2What the constraints tell us

• 1 ≤ nums.length ≤ 10⁵, and 1 ≤ k ≤ nums.length, so k can also be as big as 10⁵.
• Values can be negative (−10⁴ to 10⁴). So don't start a max at 0: start it from a real item of the window.
• With n and k both large, a "for each window, scan k items" approach can reach about 10⁹ steps (see step 9). Over the ~10⁸ limit → we need O(n) or close.

3Intuition

For each start i, look at the k items nums[i..i+k−1], find the biggest one, write it at res[i].

4Building the logic, the way the teacher does

5Approach steps

1. Make res of size n − k + 1.
2. For each start i from 0 to n − k: mx = nums[i].
3. For j from i to i + k − 1: mx = max(mx, nums[j]).
4. res[i] = mx. Return res.

6Code (Python)

class Solution:
    def maxSlidingWindow(self, nums, k):
        n = len(nums)
        res = [0] * (n - k + 1)              # one answer per window
        for i in range(n - k + 1):           # i = start of the window, up to n - k
            mx = nums[i]                     # start from a real item (values can be negative)
            for j in range(i, i + k):        # exactly the k items of this window
                mx = max(mx, nums[j])
            res[i] = mx
        return res

7Code line by line

8Dry run

Every window re-reads k − 1 items that the previous window already read. That's the waste.

9Complexity & remember

• Time: about (n − k) windows × k items each = n·k − k². The teacher's example: n = 10⁵, k = 10⁴ → 10⁹ − 10⁸ ≈ 9·10⁸. The k² part doesn't help much; this is far above 10⁸ → TLE.
• Space O(1) extra, besides the answer list.

Part B · Why a plain slide fails, and the heap idea

1The question

Same question. Now we try to slide the window instead of rescanning it.

2What the constraints tell us

n up to 10⁵. An O(n log n) solution is about 10⁵ × 17 ≈ 1.7·10⁶ steps, fine. O(n) is even better.

3Intuition: try the normal slide with one "max" variable

A normal fixed window keeps one running value and updates it: add the new item, remove the old item. Let's keep one variable mx.

• Window 1 [1, 3, −1]: mx = 3.
• Slide: −3 comes in, 1 leaves. The item leaving (1) wasn't the max, so we just compare: max(3, −3) = 3 ✓. Easy.
• Slide: 5 comes in, 3 leaves, and 3 was the max. Here max(…, 5) = 5 happens to save us. But suppose that 5 were −5: the window is [−1, −3, −5]. We know 3 is gone, but who's the new max? One variable can't tell us. We'd have to scan the whole window again, and then it's the brute force again.

So the problem is: when the max leaves, we need the second max, then maybe the third… We need a structure that keeps the window's values in order.

4The heap idea

A max-heap (priority queue) always gives the biggest item it holds in O(1), and adding or removing an item costs O(log size) because it has to rearrange itself to keep the biggest on top. So the heap does the "first max, second max, third max…" bookkeeping for us.

• Window [1, 3, −1]: heap has 3, 1, −1 → top 3.
• 1 leaves, −3 comes in: heap 3, −1, −3 → top 3.
• 3 leaves, −5 comes in (the bad case): heap −1, −3, −5 → top −1 ✓. The heap gave us the "second max" automatically.

5Approach steps

1. For each right: push (−nums[right], right).
2. While the top's index ≤ right − k (outside the window): pop it.
3. If right ≥ k − 1 (the window is full): the answer is −heap[0][0].

6Code (Python)

import heapq

class Solution:
    def maxSlidingWindow(self, nums, k):
        heap = []                                    # items: (-value, index)
        res = []
        for right in range(len(nums)):
            heapq.heappush(heap, (-nums[right], right))
            while heap[0][1] <= right - k:           # top has left the window
                heapq.heappop(heap)
            if right >= k - 1:                       # window is full
                res.append(-heap[0][0])              # biggest value in the window
        return res

7Code line by line

The heap never runs empty in that while: the item we just pushed has index right, which is always inside the window, so the loop stops at it at the latest.

8Dry run (the teacher's "−5" variation)

nums = [1, 3, −1, −3, −5], k = 3. Heap shown as real values, biggest first.

Notice the 1 (index 0) stayed in the heap from step 2 to step 5 even though it left the window early. That's lazy deletion: harmless, because it wasn't on top.

9Complexity & remember

• Time O(n log n): n pushes, at most n pops, each O(log n).
• Space O(n): with lazy deletion, old items can pile up (e.g. an increasing array never pops anything).

Part C · Optimal: the monotonic deque

1The question

Same question, now in O(n): each item should be added once and removed at most once, each in O(1).

2What the constraints tell us

n up to 10⁵ → O(n) is about 2·10⁵ deque operations. Instant.

3Intuition: who can still become a max?

The teacher starts again from the beginning and asks of every stored item: "can this ever be the answer in the future?"

• We store 1. Then 3 arrives. 3 is bigger, and 3 is newer (further right). The window only moves right, so 1 will leave the window before 3 does. Any future window that contains 1 also contains 3, and 3 beats 1. So 1 can never be a max again → delete it.
• Then −1 arrives. It's smaller than 3, but we must keep it. Why? Because 3 is older and will leave first. After 3 leaves, −1 might be the biggest. In the "−5" version, the window [−1, −3, −5] has max −1. If we hadn't stored −1, we couldn't answer that window.

Following this rule, the stored values are always decreasing from front to back. So the front is the biggest → the answer is read from the front.

4Building the logic, the way the teacher does

The proof: why the smaller items behind can never be the max again

Say index j is in the deque, a new index r arrives (r > j), and nums[j] < nums[r].

1. Windows only move to the right. A window that contains j covers some range [s, s+k−1] with s ≤ j.
2. From now on, every window we look at ends at r or later. If it still contains j, then it starts at or before j < r and ends at or after r, so it also contains r.
3. In that window, nums[r] > nums[j], so j is not the max.
4. Once a window no longer contains j, j can't be its max anyway.

So j is useless forever → popping it loses nothing. Each pop is permanent and safe.

Why store indexes, not values?

We need to know when the front item has left the window, and only its index tells us where it sits. The values we can always read back with nums[index]. The teacher stresses this: she draws values on the board for clarity, but the deque really holds indexes.

When does the front leave the window?

The window ending at right is right − k + 1 .. right. The front index is out if it's ≤ right − k. The teacher checks it as a distance: at right = 3 the front is index 1 (value 3): 3 − 1 = 2, a window of length 3 → still inside, keep it. At right = 4: 4 − 1 = 3, which would mean a length of 4 → too long, remove it.

Why a deque?

We add at the back, pop small items from the back, and pop expired items from the front. Working at both ends in O(1) is exactly what a deque does. Unlike a heap, it never rearranges anything, so it's O(1) per operation. That's why it beats the heap.

5Approach steps

1. Make res of size n − k + 1 and an empty deque of indexes.
2. For each right: while the deque isn't empty and the value at its back is smaller than nums[right], pop from the back.
3. Append right at the back.
4. If the front index ≤ right − k, pop it from the front (it has left the window).
5. If right ≥ k − 1: res[right − k + 1] = nums[front].
6. Return res.

6Code (Python)

from collections import deque

class Solution:
    def maxSlidingWindow(self, nums, k):
        n = len(nums)
        res = [0] * (n - k + 1)
        dq = deque()                         # indexes; their values decrease front -> back
        for right in range(n):
            # smaller items at the back can never be a max again
            while dq and nums[dq[-1]] < nums[right]:
                dq.pop()
            dq.append(right)
            # the front has slid out of the window right-k+1 .. right
            while dq[0] <= right - k:
                dq.popleft()
            # from right = k-1 on, every step completes a window
            if right >= k - 1:
                res[right - k + 1] = nums[dq[0]]
        return res

7Code line by line

8Dry run 1: [1, 3, −1, −3, 5, 3, 6, 7], k = 3

Deque shown as index:value, front on the left.

The deque after every step (values; the yellow box is the front = the window's max):

The window on the array at two key moments:

Final answer [3, 3, 5, 5, 6, 7] ✓.

Dry run 2: the "−5" version, where the front really expires

nums = [1, 3, −1, −3, −5], k = 3. Steps r = 0..3 are the same as above (deque [3, −1, −3], answers 3, 3).

Answer [3, 3, −1] ✓. If we had thrown −1 away at r = 2 just because it was smaller than 3, we'd have nothing left to answer this window.

9Complexity & remember

• Time O(n): there are while loops inside the for, but every index is appended once and popped at most once (from the back or from the front). Total work ≈ 2n → O(n). The brute force is O(n·k), which becomes O(n²) for large k.
• Space O(k): the deque only holds indexes from the current window, so at most k of them (plus the answer list of n − k + 1).

Part D · Revision page

s = Solution()
print(s.maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3))   # [3, 3, 5, 5, 6, 7]
print(s.maxSlidingWindow([1, 3, -1, -3, -5], 3))           # [3, 3, -1]
print(s.maxSlidingWindow([1], 1))                          # [1]
print(s.maxSlidingWindow([4, 2, 9, 1], 4))                 # [9] (k = n: one window)
print(s.maxSlidingWindow([5, 4, 3, 2, 1], 2))              # [5, 4, 3, 2]

Based on this video: Sliding Window Maximum | Monotonic Deque