beingsde
Sign In
Back to all DSA patterns
Stack•Pattern: Monotonic Stack•Medium

Largest rectangle in histogram

Problem Intuition & Objective

Find the largest rectangular area that can be formed within a bar chart.

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

Monotonic Stack: popping reveals the left boundary for each bar.

Core Invariants & Edge Cases

  • Use a monotonic increasing stack of bar indices
  • When a shorter bar is encountered, pop and calculate width from previous stack top
  • Append a sentinel bar of height 0 to flush the stack at the end
Previous ProblemDaily temperatures — next warmer dayNext Problem Implement a Min Stack with O(1) getMin()

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.