Skip to main content

Min Stack

Learn Min Stack (Stack, Data Structures & Algorithms) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.

A Stack That Also Tracks Its Minimum, in O(1) Design a stack supporting push , pop , top , AND getMin - all O(1). The obvious idea (scan the stack for the minimum) is O(n) per query. The trick: maintain a SECOND stack that tracks the minimum-so-far at each point in time, growing and shrinking in lockstep with the main stack.

More lessons in Stack