Design a stack that supports getMin in O(1)

Easy

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]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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]; }
}