Sliding Window Maximum

Free with account Updated Nov 19, 2026 · 6 min read
On this page

    Problem statement

    Given an array of integers nums and a window size k, return the maximum of every contiguous window of length k, from left to right. There are n − k + 1 windows. A frequent second part: return the length of the longest subarray in which the largest and smallest values differ by at most limit.

    This is the problem that introduces the monotonic deque, a structure that keeps "the best candidate so far" while items both enter and leave. Once you know it, the second part (a variable-size window that needs both its max and its min) takes a few extra lines. Original problems: LeetCode 239 and LeetCode 1438.

    Example

    With k = 3 there are six windows; the highlighted window [1, 4, 7] has maximum 7.
    With k = 3 there are six windows; the highlighted window [1, 4, 7] has maximum 7.
    Input:  nums = [3, 9, 1, 4, 7, 2, 6, 5], k = 3
    Output: [9, 9, 7, 7, 7, 6]
    Part 2
    Input:  nums = [6, 2, 4, 9, 7, 8, 3], limit = 2
    Output: 3          # [9, 7, 8]: max 9, min 7

    Constraints (assumed)

    • 1 ≤ k ≤ n ≤ 10⁵.
    • −10⁴ ≤ nums[i] ≤ 10⁴; values may repeat.

    What this question tests

    • Seeing why a plain sliding window (add one, remove one) fails for max: removing the current max loses information.
    • The monotonic deque: which elements can be thrown away for good, and why each is pushed and popped at most once.
    • Index bookkeeping: knowing when the front has left the window.

    Questions to ask first

    1. Can k be larger than n? (Here: no, 1 ≤ k ≤ n.)
    2. Are there duplicates? They decide whether you pop on < or ≤; both work if you store indices.
    3. Is the input a fixed array or a stream? The deque works for streams too.
    4. For part 2, is the limit inclusive? (Here: max − min ≤ limit.)