Practice › Stack & Queue
Min Stack
Medium · Stack & Queue · Asked at Amazon, Microsoft, Google, Bloomberg
Design a stack that supports push x, pop, top and getMin, each in O(1). Process the operations and print the result of every top and getMin. All pop, top and getMin operations are done on a non-empty stack.
Input
First line: q. Next q lines: one operation each.
Output
One line for every top or getMin operation.
Constraints
- 1 ≤ q ≤ 10^5
- -10^9 ≤ x ≤ 10^9
Keep a second stack (or store pairs) with the minimum so far.
Example 1
Input
6 push -2 push 0 push -3 getMin pop getMin
Output
-3 -2
Example 2
Input
3 push 5 top getMin
Output
5 5
Hints
- Scanning the stack for the minimum is O(n) per query.
- Store, next to every value, the minimum of the stack at the moment it was pushed. getMin is then just the top's stored minimum.
Approach
Each stack entry is a pair (value, minSoFar), where minSoFar = min(value, previous top's minSoFar). A pop removes the pair, so the minimum below it comes back automatically. All four operations are O(1). Read the operations as words, and print the results for top and getMin together at the end.
Complexity: O(1) per operation · O(q) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> q;
vector<pair<long long, long long>> st; // (value, min so far)
while (q--) {
string op;
cin >> op;
if (op == "push") {
long long x;
cin >> x;
long long m = st.empty() ? x : min(x, st.back().second);
st.push_back({x, m});
} else if (op == "pop") {
st.pop_back();
} else if (op == "top") {
cout << st.back().first << "\n";
} else {
cout << st.back().second << "\n";
}
}
return 0;
}Python solution
import sys
tokens = sys.stdin.read().split()
q = int(tokens[0])
stack, out, pos = [], [], 1 # stack holds (value, min so far)
for _ in range(q):
op = tokens[pos]
pos += 1
if op == "push":
x = int(tokens[pos])
pos += 1
stack.append((x, min(x, stack[-1][1]) if stack else x))
elif op == "pop":
stack.pop()
elif op == "top":
out.append(stack[-1][0])
else:
out.append(stack[-1][1])
print("\n".join(map(str, out)))Java solution
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int q = Integer.parseInt(br.readLine().trim());
long[] vals = new long[q], mins = new long[q]; // (value, min so far)
int size = 0;
StringBuilder sb = new StringBuilder();
for (int i = 0; i < q; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
String op = st.nextToken();
if (op.equals("push")) {
long x = Long.parseLong(st.nextToken());
vals[size] = x;
mins[size] = size == 0 ? x : Math.min(x, mins[size - 1]);
size++;
} else if (op.equals("pop")) {
size--;
} else if (op.equals("top")) {
sb.append(vals[size - 1]).append('\n');
} else {
sb.append(mins[size - 1]).append('\n');
}
}
System.out.print(sb);
}
}