WhiteBox
DSA
Start coding DSA Beyond LeetCode System Design AI Engineering White Room
RoadmapProblem sets
Quizzes Dan Ladder Contests Templates Graph Editor
Guides Library
Login Sign up
Sign up Log in

Workspaces

Start coding DSA Beyond LeetCode System Design AI Engineering White Room

DSA

Overview Roadmap Problem sets Quizzes Dan Ladder Contests Templates Graph Editor CP Guessr

Library

Library Guides

Community

Leaderboard Contributors Refer & Earn Cosmetics

Tools

Resume Reviewer Job Boards Changelog

Arrays and searching 0/120

DSA 0 of 360 problems solved
0%
Overview

Curriculum

    1. Hashing 0/11
    2. Two pointers 0/12
    3. Sliding window 0/21
      1. Sliding window technique 0/20
      2. Monotonic queue 0/1
    4. Prefix sums 0/29
    5. Binary search 0/20
    6. Heaps 0/11
    7. Greedy and intervals 0/9
    8. Linked lists 0/8
    9. Data structure design
  1. DSA
  2. / Arrays and searching

Sliding window · 2 of 2

Monotonic queue

Keep a moving window's maximum and minimum with two deques of indices, so the whole scan takes linear time.

2,030 words · 10 min read

Lesson Problems1 Reading4

Books1

  • Competitive Programmer’s Handbook, Section 8.3 Pages 81 and 82 find every fixed window's minimum in O(n) with the same deque. (opens in a new tab)

Links2

  • usaco.guide Sliding Window Keeps the maximum of a fixed-length window three ways: with a sorted set, a monotonic deque and two stacks. Its With Two Pointers section solves Playlist with a window that holds a set. usaco.guide (opens in a new tab)
  • cp-algorithms.com Minimum stack / Minimum queue Three ways to keep a queue’s minimum as elements enter and leave. The third is the two-stack queue. cp-algorithms.com (opens in a new tab)

More links1

  • CF Blog — Monotonic Queuecodeforces.com (opens in a new tab)
Lesson: Monotonic queue
Overview Roadmap Problem sets Log in