AI InterviewSearch…Search problems, topics, or pages…Ctrl KGet started

Topic

Monotonic Queue coding problems

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.

12 problems · 5 medium · 7 hard · judged by hidden tests in 13 languages

12problems

0 easy

5 medium

7 hard

Sign in to tick off what you solve.

Study plan: 8 problems · about 5 h 40 min

Start the study plan

Next up: Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

How it works

Monotonic Queue, step by step

Sliding window maximum, with a monotonic deque

nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3

nums1031-12-3354356677maxnone until the window is fulldequeempty

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.

0:01 / 0:38Step 1 of 10
Transcript · 10 steps

Study plan

Learn monotonic queue in 6 days

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.

  1. Day 1

    about 50 min

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

  2. Day 2

    about 1 h 10 min

    More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

  3. Day 3

    about 1 h 10 min

    More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

  4. Day 4

    about 50 min

    Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.

  5. Day 5

    about 50 min

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

  6. Day 6

    about 50 min

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

    Next topic: Matrix

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

nums1031-12-3354356677max335567deque7i=7front
Sliding window maximum, with a monotonic deque. Example: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
  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

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.

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.

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

All monotonic queue problems

Medium (5)

Hard (7)

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