42. Min Stack
Build a stack that supports adding a value, removing and returning the top value, inspecting the top, reporting the minimum, and reporting the size. Minimum queries must remain efficient as values are added and removed.
Repeated minimum values must be tracked correctly. The empty-stack operations and their exceptions are part of the public behavior described below.
Example 1
Input
push(3), push(1), push(1), pop(), getMin()
Output
pop returns 1; minimum remains 1
Explanation: The remaining equal minimum belongs to its own saved node.
Example 2
Input
push(-2147483648), push(2147483647), getMin()
Output
-2147483648
Explanation: Comparisons handle extremes without arithmetic encoding.
Constraints
0 <= operation count, live stack size <= 105-231 <= value <= 231 - 1- pop, top and getMin require a nonempty stack.
Hints
Hint 1
What information must reappear when the top node is removed?
Hint 2
Can every node save the minimum of its own remaining suffix?
Hint 3
Push a value/minimum/next node; pop restores the old head.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Duplicate minima restore at each pop
[["push",3],["push",1],["push",1],["push",2],["getMin"],["pop"],["pop"],["getMin"],["pop"],["getMin"]]
[null,null,null,null,1,2,1,1,1,3]