Design a stack that supports getMin in O(1)
Problem
Design a stack that supports push, pop, top and getMin (return the current minimum), each in O(1) time. The hard version allows only O(1) extra space.
Example 1
Input: push(-2), push(0), push(-3), getMin(), pop(), top(), getMin() Output: -3, 0, -2
Also asked as: min stack · Design a Stack that supports getMin() in O(1) time and O(1) extra space
Test cases
Case 1
Input: new MinStack() .push(-2) .push(0) .push(-3) .getMin() .pop() .top() .getMin() Expected: [null,null,null,-3,null,0,-2]
Case 2
Input: new MinStack() .push(5) .push(3) .push(7) .getMin() .pop() .pop() .getMin() Expected: [null,null,null,3,null,null,5]
Case 3
Input: new MinStack() .push(1) .push(1) .pop() .getMin() .top() Expected: [null,null,null,1,1]
View solutionHide solution1 approach
1. Parallel min-stack
Time O(1) per opSpace O(n)
Each entry also stores the minimum of the stack up to that point.
class MinStack { constructor() { this.s = []; } push(x) { this.s.push([x, this.s.length ? Math.min(x, this.getMin()) : x]); } pop() { this.s.pop(); } top() { return this.s[this.s.length - 1][0]; } getMin() { return this.s[this.s.length - 1][1]; }}