beingsde
Sign In
Back to all DSA patterns
Queue / Deque•Pattern: Monotonic Deque•Medium

Sliding window maximum using a deque

Problem Intuition & Objective

Find the maximum in every sliding window of size k in O(n).

Time ComplexityO(n)
Optimal
Space ComplexityO(k)
Memory Bounds
Optimal Algorithmic Approach

Monotonic Deque: the front always holds the index of the current window's max.

Core Invariants & Edge Cases

  • Use a monotonic decreasing deque of indices
  • Remove indices outside the window from the front
  • Remove smaller elements from the back before adding new element
Previous ProblemEvaluate Reverse Polish Notation (RPN)Next Problem Binary tree level-order traversal (BFS)

System Design & Architecture Roadmap

Coding interviews are only 50% of the bar. Master High-Level Design, distributed systems, and Object-Oriented LLD.

60+ HLD QuestionsSharding, caching, and real-time distributed systems.27 LLD BlueprintsObject-oriented design patterns with class diagrams.SDE Quick ReferenceLatency numbers and database selection matrix.