This approach utilizes two stacks. One stack will hold the main elements, while the other stack will keep track of the minimum elements. When you push a value, it's added to the main stack, and if it's less than or equal to the current minimum, it's also pushed onto the min stack. During a pop operation, if the value being popped is the current minimum, it's also popped from the min stack.
Time Complexity: O(1) for each operation.
Space Complexity: O(n), where n is the number of elements in the stack.
1import java.util.Stack;
2
3class MinStack {
4 private Stack<Integer> stack;
5 private Stack<Integer> minStack;
6
7 public MinStack() {
8 stack = new Stack<>();
9 minStack = new Stack<>();
10 }
11
12 public void push(int val) {
13 stack.push(val);
14 if (minStack.isEmpty() || val <= minStack.peek()) {
15 minStack.push(val);
16 }
17 }
18
19 public void pop() {
20 if (stack.peek().equals(minStack.peek())) {
21 minStack.pop();
22 }
23 stack.pop();
24 }
25
26 public int top() {
27 return stack.peek();
28 }
29
30 public int getMin() {
31 return minStack.peek();
32 }
33}
34The Java solution uses two Stack objects. The first is a regular stack, and the second is used to track the minimum element values. For every push, we check if the value is lower or equal to the current minimum, if yes, push it onto minStack. During pop, if the top value equals the top of minStack, pop from minStack too.
This approach reduces space usage by storing a pair (value, minimum so far) in a single stack. Each element maintains the current minimum alongside its actual value, providing quick minimum retrieval by just examining the top of the stack.
Time Complexity: O(1) for each operation.
Space Complexity: O(n), each element only holds a pair so space is efficient relative to the number of elements.
1class MinStack:
2 def __init__(self):
3 self.stack = []
4
5 def push(self, val: int) -> None:
6 if not self.stack:
7 self.stack.append((val, val))
8 else:
9 self.stack.append((val, min(val, self.stack[-1][1])))
10
11 def pop(self) -> None:
12 self.stack.pop()
13
14 def top(self) -> int:
15 return self.stack[-1][0]
16
17 def getMin(self) -> int:
18 return self.stack[-1][1]
19Python takes advantage of tuples to store both the value and current minimum together. When popping or retrieving the top, the value is easily accessible, and minimum retrieval likewise by referring to the second element of the tuple.