Monotonic Deque for Sliding Window Max/Min

You are given an array of integers and a window size k. As the window slides from left to right, one position at a time, you must report the maximum element in each window. This is LeetCode 239 (Sliding Window Maximum), and it is one of the most instructive problems in the entire canon because the optimal solution requires a data structure, the monotonic deque, that appears nowhere in a typical algorithms textbook but shows up constantly in competitive programming and interviews.

Why the Naive Approach Is Too Slow

The brute-force solution is straightforward: for each of the roughly n - k + 1 windows, scan all k elements to find the maximum. That is $O(nk)$ time. When n is 100,000 and k is 50,000, you are looking at billions of operations. We need to do better.

Why a Max-Heap Does Not Quite Work

A natural improvement is to maintain a max-heap of the elements in the current window. The maximum is always at the top, so reading it is $O(1)$. But when the window slides, you need to remove the element that just left, and that element is not necessarily the heap's root. It could be buried deep inside the heap, and removing an arbitrary element from a heap is $O(k)$ without extra bookkeeping.

You can work around this with "lazy deletion": leave stale elements in the heap and discard them when they surface to the top. This works and gives $O(n \log n)$ time, but it is more complex than necessary. There is a cleaner $O(n)$ solution.

The Monotonic Deque

The key insight is that you do not need to remember every element in the window, only the ones that could potentially be the maximum. If element A is to the left of element B and A is smaller than B, then A can never be the window maximum for any future window that includes B. Element B arrived later and is larger, so it dominates A in every way. You can discard A.

This leads to the monotonic deque: a double-ended queue of indices whose corresponding values are in strictly decreasing order. The front of the deque always holds the index of the largest element in the current window.

There are two cleanup rules you apply for every new element at index i:

Rule 1: Expiry from the front. If the front index is outside the current window (that is, less than i - k + 1), pop it from the front. That element has left the window and is no longer relevant.

Rule 2: Dominance from the back. While the back of the deque holds an index whose value is less than or equal to nums[i], pop it from the back. Those elements are now dominated by the new arrival and can never be a future window maximum.

After both cleanups, append i to the back. The deque now maintains decreasing order. Once the window has reached size k (that is, i >= k - 1), the front of the deque is the answer for this window position.

Step-by-Step Walkthrough

Let us trace through nums = [1, 3, -1, -3, 5, 3, 6, 7] with k = 3. We track the deque contents (showing values for clarity, though we store indices).

i = 0, val = 1: Deque is empty. Append index 0. Deque: [1]. Window not yet full.

i = 1, val = 3: Back of deque is 1, and 1 <= 3, so pop it (Rule 2). Deque is empty. Append index 1. Deque: [3]. Window not yet full.

i = 2, val = -1: Back of deque is 3, and 3 > -1, so no Rule 2 cleanup. Append index 2. Deque: [3, -1]. Window is full. Answer: 3 (front of deque).

i = 3, val = -3: Front index is 1, and 1 >= 3 - 3 + 1 = 1, so it stays (Rule 1 passes). Back is -1, and -1 > -3, so no Rule 2 cleanup. Append index 3. Deque: [3, -1, -3]. Answer: 3.

i = 4, val = 5: Front index is 1, and 1 < 4 - 3 + 1 = 2, so pop it (Rule 1). Now front is index 2 (-1), and 2 >= 2, so it stays. Back is -3, and -3 <= 5, pop. Back is -1, and -1 <= 5, pop. Deque is empty. Append index 4. Deque: [5]. Answer: 5.

i = 5, val = 3: Front index is 4, and 4 >= 3, stays. Back is 5, and 5 > 3, stays. Append index 5. Deque: [5, 3]. Answer: 5.

i = 6, val = 6: Front index is 4, and 4 >= 4, stays. Back is 3, and 3 <= 6, pop. Back is 5, and 5 <= 6, pop. Deque is empty. Append index 6. Deque: [6]. Answer: 6.

i = 7, val = 7: Front index is 6, and 6 >= 5, stays. Back is 6, and 6 <= 7, pop. Deque is empty. Append index 7. Deque: [7]. Answer: 7.

Final result: [3, 3, 5, 5, 6, 7].

Code: Sliding Window Maximum

from collections import deque

def maxSlidingWindow(nums, k):
    dq = deque()  # stores indices, values in decreasing order
    result = []

    for i, val in enumerate(nums):
        # Rule 1: remove indices that have left the window
        while dq and dq[0] < i - k + 1:
            dq.popleft()

        # Rule 2: remove indices whose values are <= current
        while dq and nums[dq[-1]] <= val:
            dq.pop()

        dq.append(i)

        # once we have a full window, record the max
        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

The code is short, but the logic is dense. Each of the two while loops looks like it could be expensive, but the amortized analysis tells a different story.

Why It Is $O(n)$

Every element is appended to the deque exactly once (the dq.append(i) line). Every element is removed from the deque at most once, either from the front (Rule 1) or from the back (Rule 2). That means the total number of popleft and pop operations across the entire run is at most n. The outer loop runs n times, and the inner while loops collectively do at most n removals, so the total work is $O(n)$. This is an amortized $O(1)$ per element, which is optimal since you must read every element at least once.

Sliding Window Minimum

For the minimum instead of the maximum, you simply flip the monotonicity. Maintain a deque where values are in increasing order. The cleanup rule becomes: remove from the back while the back value is greater than or equal to the current value. The front of the deque then holds the window minimum.

from collections import deque

def minSlidingWindow(nums, k):
    dq = deque()
    result = []

    for i, val in enumerate(nums):
        while dq and dq[0] < i - k + 1:
            dq.popleft()

        # flip: remove from back while value >= current
        while dq and nums[dq[-1]] >= val:
            dq.pop()

        dq.append(i)

        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

The only change is a single comparison operator. Everything else, the structure, the amortized analysis, the $O(n)$ runtime, carries over identically.

Longest Subarray Where Max - Min <= t

A powerful extension of the monotonic deque technique appears in LeetCode 1438, which asks for the longest contiguous subarray where the difference between the maximum and minimum elements is at most a given limit.

The idea is to maintain two deques simultaneously, one for the running maximum (decreasing) and one for the running minimum (increasing), over a variable-length window defined by a left pointer left and a right pointer right.

For each new right, update both deques as usual. Then check: is max - min > t? If so, advance left until the condition is satisfied again, popping from the front of either deque if the front index falls behind left. The length of the valid window at each step is a candidate for the answer.

from collections import deque

def longestNiceSubarray(nums, t):
    max_dq = deque()  # decreasing: front is max
    min_dq = deque()  # increasing: front is min
    left = 0
    best = 0

    for right, val in enumerate(nums):
        # maintain max deque
        while max_dq and nums[max_dq[-1]] <= val:
            max_dq.pop()
        max_dq.append(right)

        # maintain min deque
        while min_dq and nums[min_dq[-1]] >= val:
            min_dq.pop()
        min_dq.append(right)

        # shrink window until max - min <= t
        while nums[max_dq[0]] - nums[min_dq[0]] > t:
            left += 1
            if max_dq[0] < left:
                max_dq.popleft()
            if min_dq[0] < left:
                min_dq.popleft()

        best = max(best, right - left + 1)

    return best

Each element enters and exits each deque at most once, and the left pointer only moves forward, so the total work is still $O(n)$. The space is $O(n)$ in the worst case for the two deques, though in practice they stay much smaller.

Shortest Subarray with Sum at Least K

Consider LeetCode 862. Shortest Subarray with Sum at Least K, which asks for the length of the shortest contiguous subarray whose sum is at least k. Unlike the classic sliding window minimum-length subarray problem (which only works with positive numbers), this array can contain negative values.

The key idea is to work with prefix sums and a monotonic deque. Let P[i] be the prefix sum up to index i. The sum of subarray (j, i] is P[i] - P[j]. We want the shortest range where P[i] - P[j] >= k.

We maintain a deque of indices into the prefix sum array in increasing order of their prefix sum values. For each new index i:

1. Harvest answers from the front: While P[i] - P[deque[0]] >= k, we have found a valid subarray. Record its length and pop the front, since no future i can produce a shorter subarray starting at that same j.
2. Maintain monotonicity from the back: While the prefix sum at the back of the deque is >= P[i], pop it. A later index with a smaller prefix sum is strictly better as a starting point.

from collections import deque

def shortestSubarray(nums, k):
    n = len(nums)
    P = [0] * (n + 1)
    for i in range(n):
        P[i + 1] = P[i] + nums[i]

    dq = deque()
    ans = n + 1

    for i in range(n + 1):
        while dq and P[i] - P[dq[0]] >= k:
            ans = min(ans, i - dq.popleft())
        while dq and P[dq[-1]] >= P[i]:
            dq.pop()
        dq.append(i)

    return ans if ans <= n else -1

Each index enters and leaves the deque at most once, so the time complexity is $O(n)$. The monotonic deque on prefix sums is what makes this work despite negative numbers: it ensures we always consider the best possible starting points.

Constrained Subsequence Sum

With LeetCode 1425. Constrained Subsequence Sum, the goal is to find the maximum sum of a non-empty subsequence such that for every two consecutive elements in the subsequence, nums[i] and nums[j], j - i <= k.

This is a DP problem: dp[i] = nums[i] + max(0, max(dp[j] for j in [i-k, i-1])). The max over the previous k values is exactly a sliding window maximum, which the monotonic deque handles in amortized $O(1)$.

from collections import deque

def constrainedSubsetSum(nums, k):
    n = len(nums)
    dp = nums[:]
    dq = deque()  # stores indices, dp values in decreasing order

    for i in range(n):
        if dq:
            dp[i] = max(dp[i], dp[dq[0]] + nums[i])

        # remove indices outside the window
        while dq and dq[0] < i - k + 1:
            dq.popleft()

        # maintain decreasing order of dp values
        while dq and dp[dq[-1]] <= dp[i]:
            dq.pop()

        dq.append(i)

    return max(dp)

The deque maintains indices in decreasing order of their dp values. For each new index, we look at the front (the best dp value in the window) and add it to nums[i] if it is positive. Then we enforce the window size and monotonicity. Total time is $O(n)$ and space is $O(n)$.

Jump Game VI

Take LeetCode 1696. Jump Game VI: it asks for the maximum score to reach the last index, where from index i you can jump to any index in [i+1, i+k] and your score is the sum of values at visited indices.

The recurrence is dp[i] = nums[i] + max(dp[i-k], ..., dp[i-1]), identical in structure to Constrained Subsequence Sum. The monotonic deque gives the maximum in the sliding window of size k in $O(1)$ amortized time.

from collections import deque

def maxResult(nums, k):
    n = len(nums)
    dp = [0] * n
    dp[0] = nums[0]
    dq = deque([0])

    for i in range(1, n):
        # remove indices outside the window
        while dq and dq[0] < i - k:
            dq.popleft()

        dp[i] = nums[i] + dp[dq[0]]

        # maintain decreasing order of dp values
        while dq and dp[dq[-1]] <= dp[i]:
            dq.pop()
        dq.append(i)

    return dp[-1]

The pattern is the same: the deque stores indices whose dp values are in decreasing order, the front is always the best choice in the window, and both expiry and dominance rules are enforced. Time is $O(n)$ and space is $O(n)$.

Complexity Analysis

For the sliding window maximum (or minimum) with fixed window size k: time is $O(n)$, space is $O(k)$ since the deque never holds more than k indices.

For the longest subarray with max - min <= t: time is $O(n)$, space is $O(n)$ in the worst case for the two deques.

The monotonic deque is one of the most useful tools in the competitive programmer's toolkit. Whenever you find yourself needing the maximum or minimum over a sliding range, whether the window is fixed or variable, the decreasing deque for max and increasing deque for min should be your first instinct. The pattern is always the same: maintain monotonicity by evicting dominated elements from the back, and expire stale elements from the front.

Recognizing this pattern

You're probably looking at a monotonic deque when:

• You need the max or min of every sliding window of size k in O(n) total.
• A two-pointer window expands and shrinks while you must know its current max or min at every step.
• The constraint involves max − min of a window, for example, "longest subarray where max − min ≤ t."
• A heap-based solution would be O(n log n) and you need to drop the log.

Common templates:

• Fixed-window max/min: decreasing deque of indices; front is the window's max. Example: Sliding Window Maximum.
• Variable window with max − min constraint: two deques (one increasing, one decreasing) drive the shrink condition. Example: Longest Continuous Subarray With Absolute Diff ≤ Limit.
• DP with sliding window optimization: when dp[i] = max(dp[j]) + ... over a range of j, a deque speeds it up. Example: Jump Game VI.
• Bounded subarray sum: monotonic deque over prefix sums to find the shortest subarray with sum ≥ k. Example: Shortest Subarray With Sum at Least K.