Search⌘ K
AI Features
Home
Courses
Data Structures for Coding Interviews

Solution: Min Stack

Understand how to implement a min stack data structure that enables push, pop, and retrieving the minimum element in constant time. Explore the two-stack approach, where one stack stores all values and another keeps track of current minimums, ensuring O(1) time complexity for all operations and analyzing its space efficiency.

We'll cover the following...

Statement

Design a stack data structure to retrieve the minimum value in O(1)O(1) time. The following functions must be implemented:

  • min(): Returns the minimum value in the stack in constant time.
  • push(int value): Pushes a value onto the stack.
  • pop(): Removes and returns a value from the top of the stack.

All functions should be implemented with a time complexity of O(1)O(1).

Constraints:

  • −105≤-10^5 \leq
...