Monotonic Queue Coding Problems: 5 Questions with Solutions

How monotonic queue works, step by step

1. Every window of 3 needs its maximum. A deque holds indices whose values decrease from front to back, so the front is always the window's maximum; a value smaller than a newer one can never be a maximum again, so it is dropped from the back.
2. 1 enters the window at index 0. The window is not full yet.
3. 3 enters the window at index 1. 1 is no larger and will leave the window before 3 does, so it is dropped from the back. The window is not full yet.
4. -1 enters the window at index 2. It is smaller than 3, so it waits at the back in case the larger values slide out first. The front, 3, is the maximum of [1, 3, -1].
5. -3 enters the window at index 3. It is smaller than -1, so it waits at the back in case the larger values slide out first. The front, 3, is the maximum of [3, -1, -3].
6. 5 enters the window at index 4. Index 1 (3) has slid out of the window, so it leaves from the front. -3 and -1 are no larger and will leave the window before 5 does, so they are dropped from the back. The front, 5, is the maximum of [-1, -3, 5].
7. 3 enters the window at index 5. It is smaller than 5, so it waits at the back in case the larger values slide out first. The front, 5, is the maximum of [-3, 5, 3].
8. 6 enters the window at index 6. 3 and 5 are no larger and will leave the window before 6 does, so they are dropped from the back. The front, 6, is the maximum of [5, 3, 6].
9. 7 enters the window at index 7. 6 is no larger and will leave the window before 7 does, so it is dropped from the back. The front, 7, is the maximum of [3, 6, 7].
10. Every window has its maximum: [3, 3, 5, 5, 6, 7]. Each index joins the deque once and leaves at most once, from the front or the back, so the pass is O(n), where rescanning every window would be O(n·k).

Monotonic Queue study plan

3 of the 5 Monotonic Queue problems (3 hard) over 3 days, about 2 h 45 min in all — the pattern first, then easiest to hardest. After that, the other 2 in the full list below are practice at your own pace. Then move on to Matrix.

Day 1

Learn the pattern: read the essentials and step through the walkthrough above, then solve this problem.

• Sliding Window Maximum Hard

Day 2

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

• Constrained Subsequence Sum Hard

Day 3

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

• Shortest Subarray with Sum at Least K Hard

Next topic: Matrix

Monotonic Queue: the essentials

When to reach for it

The maximum or minimum of a window sliding forward: of every window of size k, of dp[j] over the last k positions, of prefix sums in the shortest subarray reaching k with negatives allowed. It is a Monotonic Stack with a second exit at the front for old indices. If elements leave out of order, use a heap with lazy deletion.

The pattern

Keep indices whose values decrease from front to back (for a maximum). Before pushing i, pop from the back every index whose value is no larger: i is newer and at least as large, so it outlasts them. Drop the front once it leaves the window; the front is the window's answer. In a DP, expire, read the front for dp[i], then push.

from collections import deque

def max_sliding_window(nums, k):
    dq, out = deque(), []               # indices; their values decrease
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:
            dq.pop()                    # beaten by a newer, larger value
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()                # fell out of the window
        if i >= k - 1: out.append(nums[dq[0]])
    return out

Cost

Each index is pushed and popped at most once: O(n) time and O(k) space, against O(n log n) for a heap of (value, index) pairs.

Common mistakes

• Storing values, not indices, so there is no telling when the front expired.
• An off-by-one in the bound: the window of size k ending at i starts at i - k + 1.
• In a DP, pushing i before reading the front, so dp[i] is computed from itself.
• In Shortest Subarray with Sum at Least K, popping the front only on expiry; it also leaves once it meets the sum, as later ends only lengthen that subarray.

Start with

• Sliding Window Maximum: the plain decreasing deque.
• Constrained Subsequence Sum: the best dp[j] among the last k positions.
• Shortest Subarray with Sum at Least K: an increasing deque of prefix sums, popped from both ends.

All monotonic queue problems

Hard (5)

• Constrained Subsequence Sum Array, Dynamic Programming, Queue
• Shortest Subarray with Sum at Least K Array, Prefix Sum, Sliding Window
• Maximum Number of Robots Within Budget Array, Sliding Window, Two Pointers
• Max Value of Equation Array, Sliding Window
• Sliding Window Maximum Array, Sliding Window, Heap

Companies that ask monotonic queue problems

• Amazon 4 problems on monotonic queue
• Google 4 problems on monotonic queue
• Meta 2 problems on monotonic queue
• Flipkart 1 problem on monotonic queue
• Microsoft 1 problem on monotonic queue

Other topics

• Arrays 667 problems
• Strings 282 problems
• Math 213 problems
• Hash Table 202 problems
• Dynamic Programming 195 problems
• Greedy 163 problems
• Sorting 156 problems
• Two Pointers 113 problems
• Matrix 107 problems
• Binary Search 95 problems
• Simulation 88 problems
• Bit Manipulation 83 problems