How to Explain Sliding Window Maximum in a Coding Interview (Step-by-Step)

Sliding Window Maximum is the problem that unlocks the monotonic deque pattern — one of the most powerful and least understood tools in the interview toolkit. The brute force is obvious. The O(n) solution requires one sharp insight: useless elements should never even make it onto the deque.

In this post, you’ll learn exactly how to walk an interviewer through LeetCode 239: what a monotonic deque is and why it fits this problem, the three deque operations in the right order, full step-by-step tracing, and every edge case worth calling out.

Problem Statement

Examples

Constraints

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104
• 1 <= k <= nums.length

What Is the Problem?

“I have a fixed-size window of width k sliding across the array one step at a time. For each window position, I need to report the maximum element. The output has n - k + 1 values. The challenge is doing this faster than O(nk) — brute-force scanning each window independently.”

Naming the output size n - k + 1 and the brute-force cost O(nk) immediately shows the interviewer you’ve framed the problem correctly before reaching for an approach.

Step 1: Compare Approaches Before Jumping to Code

“A max-heap works but requires lazy deletion — when an element leaves the window, we can’t efficiently remove it from the middle of a heap. The monotonic deque avoids this entirely: we only store indices of elements that could still be the maximum, and we evict them eagerly as they become useless.”

The Key Insight — Useless Elements Never Belong on the Deque

“Think of it this way: if I’m standing in a queue and someone taller than me joins behind me, I’ll never be seen. For maximum purposes I’m invisible for the rest of my time in the window. The deque just formalises that intuition — remove anyone who can never be the answer.”

Monotonic Deque Properties

Step 2: Explain the Algorithm in Plain English

Step-by-Step Deque Trace — nums = [1,3,-1,-3,5,3,6,7], k = 3

The deque stores indices. Values shown in parentheses for readability. Green = front (current max), blue = rest of deque.

Step 3: Talk Through the Code

from collections import deque

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        dq     = deque()   # Stores indices; front = index of current window max
        result = []

        for i in range(len(nums)):

            # 1. Evict front if it has slid out of the window
            if dq and dq[0] < i - k + 1:
                dq.popleft()

            # 2. Evict from back all indices whose values are <= nums[i]
            #    They can never be the maximum while nums[i] is in the window
            while dq and nums[dq[-1]] <= nums[i]:
                dq.pop()

            # 3. Push current index
            dq.append(i)

            # 4. Record max once first full window is formed
            if i >= k - 1:
                result.append(nums[dq[0]])

        return result

Three things worth narrating explicitly: we store indices not values (so we can check window boundaries); the front eviction happens before the back eviction (order matters — clean the front first so it’s always valid when we read it); and we only record a result once i >= k - 1, meaning the first full window has been formed.

Step 4: Highlight Edge Cases

Step 5: State Time and Space Complexity

“The inner while loop for back-eviction looks like it could make this O(n²), but it can’t. Every index is pushed onto the deque exactly once and popped at most once — either from the back during eviction, or from the front when it leaves the window. So the total number of push + pop operations across the entire run is at most 2n — O(n) overall. This is the same amortised argument as for the Longest Consecutive Sequence inner loop.”

Interview Checklist for Sliding Window Maximum

• Restate — “max of every k-element window; output has n−k+1 values”
• Name the brute-force cost O(nk) and explain why it’s too slow
• Mention max-heap O(n log k) and why lazy deletion makes it messier than it looks
• Introduce the monotonic deque — decreasing front-to-back, front is always the window max
• State the core insight — elements smaller than the incoming value can never be the max; discard them eagerly
• Store indices not values — needed to check window boundary expiry
• Describe the three operations in order: front eviction → back eviction → push → record
• Explain why back-eviction uses <= (equal values: older one is never needed again)
• Justify O(n) time with the amortised argument — each index pushed and popped at most once
• State O(k) space for the deque
• Call out edge cases: k=1, k=n, strictly decreasing, strictly increasing, duplicates

Related Problems to Practice

If you can solve Sliding Window Maximum cleanly, try these next: