Monotonic Queue Coding Problems: 12 Questions with Solutions
12 monotonic queue coding problems — 5 medium · 7 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 6-day plan.
- Problems: 12
- By difficulty: 5 medium · 7 hard
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
- Cost: Free on every plan; sign in to run and submit
A monotonic queue is a double-ended queue kept in sorted order: each new element first removes every element at the back that it beats, and elements leave from the front once they fall out of the window. The front is then always the best value in the current window — its maximum, its minimum, the best earlier dynamic-programming value — at amortised constant cost per step. The problems here practise the sliding-window maximum and its use inside dynamic programming and prefix-sum searches, where a heap would cost an extra logarithm.
How monotonic queue works, step by step
nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3- 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.
- 1 enters the window at index 0. The window is not full yet.
- 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.
- -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].
- -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].
- 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].
- 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].
- 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].
- 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].
- 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
8 of the 12 Monotonic Queue problems (5 medium and 3 hard) over 6 days, about 5 h 40 min in all — the pattern first, then easiest to hardest. After that, the other 4 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.
Day 2
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
- Continuous Subarrays Medium
- Jump Game VI Medium
Day 3
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
Day 4
Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.
Day 5
Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.
Day 6
Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.
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
istarts ati - k + 1. - In a DP, pushing
ibefore reading the front, sodp[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
Medium (5)
- Count Partitions With Max-Min Difference at Most K Array, Dynamic Programming, Queue
- Minimum Number of Coins for Fruits Array, Dynamic Programming
- Jump Game VI Array, Dynamic Programming, Queue
- Continuous Subarrays Array, Sliding Window, Ordered Set
- Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit Array, Sliding Window, Ordered Set
Hard (7)
- Find Maximum Non-decreasing Array Length Array, Binary Search, Dynamic Programming
- Delivering Boxes from Storage to Ports Array, Dynamic Programming, Segment Tree
- 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 11 problems on monotonic queue
- Google 8 problems on monotonic queue
- Microsoft 3 problems on monotonic queue
- Meta 2 problems on monotonic queue
- Capital One 1 problem on monotonic queue
- Databricks 1 problem on monotonic queue
- Directi 1 problem on monotonic queue
- Flipkart 1 problem on monotonic queue
- Nutanix 1 problem on monotonic queue
- PhonePe 1 problem on monotonic queue
- Uber 1 problem on monotonic queue
Next topic: Matrix