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

Implement a Min Stack with O(1) getMin()

Problem Intuition & Objective

Design a stack that supports push, pop, top, and retrieving the minimum in O(1).

Time ComplexityO(1) all ops
Optimal
Space ComplexityO(n)
Memory Bounds
Optimal Algorithmic Approach

Dual-stack: main stack + auxiliary min stack that only grows when a new minimum is pushed.

Core Invariants & Edge Cases

  • Maintain a secondary 'min stack' that tracks minimums
  • Push to min stack when new element ≤ current min; pop synchronously
  • Alternatively encode the delta from current min in a single stack
Previous ProblemLargest rectangle in histogramNext Problem Evaluate Reverse Polish Notation (RPN)

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.