[Leetcode] Min Stack

Use more space to improve time complexity.

Description

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

• MinStack() initializes the stack object.
• void push(int val) pushes the element val onto the stack.
• void pop() removes the element on the top of the stack.
• int top() gets the top element of the stack.
• int getMin() retrieves the minimum element in the stack.

You must implement a solution with O(1) time complexity for each function.

Examples

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

Solution

// ["MinStack", "push", "push", "push", "getMin", "pop", "top", "getMin"]
// [        [],   [-2],    [0],   [-3],       [],    [],    [],       []]
// stack          [-2]     [-2,0] [-2,0,-3]          [-2,0]
// add min(curr_min, curr) into mins_keeper
// mins_keeper   [-2]      [-2,-2][-2,-2,-3]         [-2,-2]

To keep O(1) time complexity, the stack cannot be sorted, so the challenge is how to know the min of stack after the last has been popped.

The solution is creating a mins_keeper of the same length with stack. When push or pop to stack, do the same to mins_keeper, only the elm to push is different. Always make the last of mins_keeper the min of stack at the current round. This can be divided into 2 cases.

1. The new elm to be pushed to stack is min of the slack: push it to mins_keeper as the last element.

2. The new elm isn’t min: push curr_min of stack to curr_keeper as the last element. By doing so, when all elms after new are popped, the last of mins_keeper is ensured to be the correct min since it’s the curr_min at the time.

Note the new not being curr_min at curr round has no chance to become curr_min at any round. For previous rounds, new must have been popped. For curr and subsequent rounds, curr_min or smaller is the correct min.

• code