Solution: Min Stack

Let's solve the Min Stack problem using the Custom Data Structure pattern.

Statement

Design a custom stack class, Min Stack, allowing us to push, pop, and retrieve the minimum value in constant time. Implement the following methods for Min Stack:

  • Constructor: This initializes the Min Stack object.

  • Pop(): This removes and returns from the stack the value that was most recently pushed onto it.

  • Push(): This pushes the provided value onto the stack.

  • Min Number(): This returns the minimum value in the stack in O(1)O(1) time.

Note: The time complexity of all the methods above should be O(1)O(1).

Constraints:

  • −104≤-10^{4} \leq value ≤104\leq 10^{4}

  • The Pop() and Min Number() methods will always be called on non-empty stacks.

  • At most, 10310^3 calls will be made to Push(), Pop(), and Min Number().

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.