Monotonic Queue — Interview Preparation¶

Junior Questions¶

Middle Questions¶

Senior Questions¶

Coding Challenge (3 Languages)¶

Challenge: Sliding Window Maximum¶

Given an integer array nums and a sliding window of size k, return an array of the maximum value in each window as the window moves left to right.

Constraints: - 1 <= nums.length <= 10^5 - 1 <= k <= nums.length - -10^4 <= nums[i] <= 10^4

Required: O(n) time, O(k) space.

Go¶

package main

import "fmt"

// maxSlidingWindow returns the maximum of every contiguous window of size k.
// Time:  O(n) — each index pushed once and popped at most once.
// Space: O(k) for the deque.
func maxSlidingWindow(nums []int, k int) []int {
    if len(nums) == 0 || k <= 0 {
        return nil
    }
    out := make([]int, 0, len(nums)-k+1)
    dq := make([]int, 0, k) // indices, decreasing in nums value

    for i, x := range nums {
        // Expire front if it left the window.
        if len(dq) > 0 && dq[0] < i-k+1 {
            dq = dq[1:]
        }
        // Drop back while smaller than current.
        for len(dq) > 0 && nums[dq[len(dq)-1]] < x {
            dq = dq[:len(dq)-1]
        }
        dq = append(dq, i)
        if i >= k-1 {
            out = append(out, nums[dq[0]])
        }
    }
    return out
}

func main() {
    // nums = [1,3,-1,-3,5,3,6,7], k = 3 -> [3,3,5,5,6,7]
    fmt.Println(maxSlidingWindow([]int{1, 3, -1, -3, 5, 3, 6, 7}, 3))
    // nums = [1], k = 1 -> [1]
    fmt.Println(maxSlidingWindow([]int{1}, 1))
    // nums = [9,11], k = 2 -> [11]
    fmt.Println(maxSlidingWindow([]int{9, 11}, 2))
}

Java¶

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Arrays;

public class SlidingWindowMaximum {

    /**
     * Returns the maximum of every contiguous window of size k.
     * Time:  O(n)
     * Space: O(k)
     */
    public static int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) return new int[0];
        int n = nums.length;
        int[] out = new int[n - k + 1];
        int idx = 0;
        Deque<Integer> dq = new ArrayDeque<>(k);

        for (int i = 0; i < n; i++) {
            if (!dq.isEmpty() && dq.peekFirst() < i - k + 1) {
                dq.pollFirst();
            }
            while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i]) {
                dq.pollLast();
            }
            dq.offerLast(i);
            if (i >= k - 1) {
                out[idx++] = nums[dq.peekFirst()];
            }
        }
        return out;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(
            maxSlidingWindow(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3)));
        // [3, 3, 5, 5, 6, 7]
        System.out.println(Arrays.toString(maxSlidingWindow(new int[]{1}, 1)));
        // [1]
        System.out.println(Arrays.toString(maxSlidingWindow(new int[]{9, 11}, 2)));
        // [11]
    }
}

Python¶

"""Sliding window maximum — O(n) using a monotonic deque."""

from collections import deque


def max_sliding_window(nums: list[int], k: int) -> list[int]:
    """Return the maximum value of every window of size k.

    Time:  O(n) — each index is pushed and popped at most once.
    Space: O(k) for the deque.
    """
    if not nums or k <= 0:
        return []
    out: list[int] = []
    dq: deque[int] = deque()  # indices, decreasing in nums value
    for i, x in enumerate(nums):
        if dq and dq[0] < i - k + 1:
            dq.popleft()
        while dq and nums[dq[-1]] < x:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            out.append(nums[dq[0]])
    return out


if __name__ == "__main__":
    print(max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3))  # [3, 3, 5, 5, 6, 7]
    print(max_sliding_window([1], 1))                          # [1]
    print(max_sliding_window([9, 11], 2))                      # [11]

Walkthrough to give the interviewer:

"I keep a deque of indices, decreasing in the value they point into nums. The front of the deque always holds the index of the current window's max. On each new element I first expire the front if it left the window, then drop from the back any indices whose value is dominated by the new one — those can never be the max again. Push the new index, record the front as the answer if the window is full. Each index is pushed once and popped at most once, so total work is O(n)."

Follow-up the interviewer may ask:

"What if I asked for the minimum instead?" — Use an increasing deque; flip the back-pop comparison to >.

"What if I asked for the second-largest?" — A single deque does not give you the second-largest. Use a two-heap approach or a sorted multiset with lazy deletion.

"What if k changes between queries?" — Static array, varying k -> use a sparse table, not a deque.

"Can you do it in O(1) memory?" — No. The output alone is n - k + 1 values; just storing it is O(n - k). The working set is O(k), which is minimal for any window-aware algorithm.