Sliding Window Maximum — Google Monotonic Deque Interview Question

Problem Statement#

Given an integer array nums and an integer k, return the maximum value in every contiguous window of length k as the window slides from left to right.

Constraints:

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
• 1 <= k <= nums.length
• Single pass required for the optimal solution

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

Input:  nums = [1], k = 1
Output: [1]

Why This Problem Matters#

This is LeetCode 239 Sliding Window Maximum and it shows up in Google phone screens and onsite rounds repeatedly. Google interviewers like it because the brute-force O(n times k) is obvious, the heap solution at O(n log k) feels right but is suboptimal, and the monotonic deque at O(n) is the proper answer. The problem rewards candidates who understand amortised analysis — every element enters and leaves the deque at most once.

The Core Insight#

Maintain a deque of indices whose values are strictly decreasing from front to back. The front of the deque is always the index of the current window maximum.

Two invariants make this work. Before pushing a new index i, pop indices off the back while their values are less than or equal to nums[i] — those values can never be the max again because a larger or equal value sits to their right. After pushing, pop from the front if its index falls outside the current window — front <= i - k.

Once i reaches k - 1, the deque has been initialised and you can record nums[deque.front()] for every step.

Visual Dry Run#

Solution (Optimal)#

from collections import deque
 
class Solution:
    def maxSlidingWindow(self, nums, k):
        dq = deque()
        out = []
        for i, n in enumerate(nums):
            while dq and nums[dq[-1]] <= n:
                dq.pop()
            dq.append(i)
            if dq[0] <= i - k:
                dq.popleft()
            if i >= k - 1:
                out.append(nums[dq[0]])
        return out

var maxSlidingWindow = function(nums, k) {
    const dq = [], out = [];
    for (let i = 0; i < nums.length; i++) {
        while (dq.length && nums[dq[dq.length - 1]] <= nums[i]) dq.pop();
        dq.push(i);
        if (dq[0] <= i - k) dq.shift();
        if (i >= k - 1) out.push(nums[dq[0]]);
    }
    return out;
};

Time: O(n) — each index is pushed once and popped at most once Space: O(k) — the deque holds at most one window's worth of indices

Common Mistakes#

• Storing values in the deque instead of indices, losing the ability to evict by window position
• Using strict less-than instead of less-than-or-equal when popping, causing duplicate dominators
• Forgetting to evict expired front indices on every step
• Recording the max before the first full window forms — start at index k - 1
• Reaching for a heap (O(n log k)) and stopping there without seeing the deque optimisation

Interview Tips#

• Mention all three approaches in order — brute force, heap, deque — then pick deque
• State amortised O(n) explicitly — each index enters once, leaves once
• Draw the deque on the whiteboard alongside the array for clarity
• Note that shift is O(n) in JavaScript arrays — use a head pointer or a real deque structure for production
• Explain why you compare with less-than-or-equal — equal values are safely evicted because the new index dominates

Follow-up Questions#

• Return the sliding window minimum. (Hint: monotonic increasing deque)
• Stream version — values arrive one by one. (Hint: same deque, emit per arrival)
• Sliding window median. (Hint: two heaps with lazy deletion)
• Find the max sum of any length-k subarray. (Hint: simple prefix sum, no deque needed)
• Generalise to a 2D matrix with k by k window. (Hint: apply 1D deque per row, then per column)

Key Takeaways#

• LeetCode 239 is a Google interview favourite at the hard tier
• Monotonic decreasing deque gives amortised O(n) time
• Store indices, not values, so you can evict expired entries by position
• Brute force is O(n times k); heap is O(n log k); deque is O(n)
• Less-than-or-equal eviction keeps the deque strictly decreasing
• The pattern generalises to sliding window minimum and other range-extreme problems
• Use a real deque or head pointer in production — array shift is O(n)