Max Stack
Description
Design a stack that can also find and remove its largest value.
Implement the MaxStack class:
MaxStack()starts an empty stack.void push(int x)pushesxonto the stack.int pop()removes the value on top of the stack and returns it.int top()returns the value on top without removing it.int peekMax()returns the largest value in the stack without removing it.int popMax()removes the largest value and returns it. If several values are equal to the largest, it removes only the one nearest the top.
The stack holds at least one value whenever pop, top, peekMax or popMax is called.
Follow-up: can top take O(1) time and every other call O(log n)?
Examples
Example 1
Input:
["MaxStack", "push", "push", "push", "top", "popMax", "top", "peekMax", "pop", "top"]
[[], [5], [1], [5], [], [], [], [], [], []]
Output: [null, null, null, null, 5, 5, 1, 5, 1, 5]
Explanation: After 5, 1 and 5 the top is 5. popMax takes the 5 nearer the top, the one pushed last, so the top is 1 and the largest is still 5. pop takes the 1, and the first 5 is on top again.
Example 2
Input:
["MaxStack", "push", "push", "push", "push", "popMax", "pop", "top", "popMax", "top"]
[[], [2], [7], [7], [3], [], [], [], [], []]
Output: [null, null, null, null, null, 7, 3, 7, 7, 2]
Explanation: Two equal largest values: popMax takes the upper 7 and leaves 2, 7, 3. pop takes the 3, the other 7 is on top, and popMax takes it, leaving 2.
Example 3
Input:
["MaxStack", "push", "peekMax", "popMax", "push", "push", "top", "peekMax", "pop", "top"]
[[], [-4], [], [], [-9], [-1], [], [], [], []]
Output: [null, null, -4, -4, null, null, -1, -1, -1, -9]
Explanation: One value, −4, is both the top and the largest, and popMax empties the stack. Then −9 and −1 go in: −1 is the top and the largest, and after pop, −9 is left.
Constraints
- −10⁷ ≤ x ≤ 10⁷
- At most 10⁵ calls are made to push, pop, top, peekMax and popMax
- The stack holds at least one value whenever pop, top, peekMax or popMax is called
Editorial
Brute Force
Intuition
A stack answers push, pop and top already. For the largest value, keep a second stack beside it: each entry of maxes is the largest of the values from the bottom up to that point, so its top is the largest in the stack. popMax is the hard one. The largest value can be anywhere, so dig: pop values into a buffer until the largest is on top, take it, then push the buffer back.
Step-by-Step Explanation
Let's trace Example 2, which digs:
push(2)goes onvalues, and onmaxestoo, since nothing is below it.push(7)goes onvalues, andmaxesgets 7, the larger of 7 and 2.push(7)goes onvalues, andmaxesgets 7, the larger of 7 and 7.push(3)goes onvalues, andmaxesgets 7, the larger of 3 and 7.popMax()digs 1 value out to reach 7, takes it, and pushes it back.pop()takes 3 off both stacks.top()reads the top ofvalues, 7.popMax()finds 7 right on top and takes it.top()reads the top ofvalues, 2.
Two Stacks and a Dig — Every push keeps the running largest beside it; popMax moves the values above the largest out and back.
Algorithm
- Keep the values in a stack, and beside it a stack
maxesof running maxima. - push adds
xto the values and the larger ofxand the top ofmaxestomaxes; pop takes both tops. - top reads the top of the values; peekMax reads the top of
maxes. - popMax: pop values into a buffer until the top is the largest, pop it, then push every buffered value back, last popped first.
Code
class MaxStack {
vector<int> values, maxes; // maxes[i] is the largest of values[0..i]
public:
MaxStack() {
}
void push(int x) {
values.push_back(x);
maxes.push_back(maxes.empty() ? x : max(x, maxes.back()));
}
int pop() {
int x = values.back();
values.pop_back();
maxes.pop_back();
return x;
}
int top() {
return values.back();
}
int peekMax() {
return maxes.back();
}
int popMax() {
int m = maxes.back();
vector<int> buffer;
while (values.back() != m) buffer.push_back(pop()); // dig down to the largest
pop();
while (!buffer.empty()) { // and put the rest back
push(buffer.back());
buffer.pop_back();
}
return m;
}
};
class MaxStack:
def __init__(self):
self.values = []
self.maxes = [] # maxes[i] is the largest of values[0..i]
def push(self, x: int) -> None:
self.values.append(x)
self.maxes.append(max(x, self.maxes[-1]) if self.maxes else x)
def pop(self) -> int:
self.maxes.pop()
return self.values.pop()
def top(self) -> int:
return self.values[-1]
def peekMax(self) -> int:
return self.maxes[-1]
def popMax(self) -> int:
m, buffer = self.maxes[-1], []
while self.values[-1] != m: # dig down to the largest
buffer.append(self.pop())
self.pop()
for x in reversed(buffer): # and put the rest back
self.push(x)
return m
class MaxStack {
private int[] values = new int[16], maxes = new int[16]; // maxes[i] is the largest of values[0..i]
private int[] buffer = new int[16]; // where popMax keeps the values above the largest
private int size = 0;
public MaxStack() {
}
public void push(int x) {
if (size == values.length) {
values = Arrays.copyOf(values, 2 * size);
maxes = Arrays.copyOf(maxes, 2 * size);
}
values[size] = x;
maxes[size] = size == 0 ? x : Math.max(x, maxes[size - 1]);
size++;
}
public int pop() {
return values[--size];
}
public int top() {
return values[size - 1];
}
public int peekMax() {
return maxes[size - 1];
}
public int popMax() {
int m = maxes[size - 1], b = 0;
if (buffer.length < size) buffer = new int[values.length];
while (values[size - 1] != m) buffer[b++] = pop(); // dig down to the largest
pop();
while (b > 0) push(buffer[--b]); // and put the rest back
return m;
}
}
var MaxStack = function() {
this.values = [];
this.maxes = []; // maxes[i] is the largest of values[0..i]
};
MaxStack.prototype.push = function(x) {
this.values.push(x);
this.maxes.push(this.maxes.length ? Math.max(x, this.maxes[this.maxes.length - 1]) : x);
};
MaxStack.prototype.pop = function() {
this.maxes.pop();
return this.values.pop();
};
MaxStack.prototype.top = function() {
return this.values[this.values.length - 1];
};
MaxStack.prototype.peekMax = function() {
return this.maxes[this.maxes.length - 1];
};
MaxStack.prototype.popMax = function() {
const m = this.maxes[this.maxes.length - 1], buffer = [];
while (this.values[this.values.length - 1] !== m) buffer.push(this.pop()); // dig down to the largest
this.pop();
while (buffer.length) this.push(buffer.pop()); // and put the rest back
return m;
};
Complexity Analysis
Time Complexity: O(1) for each call but popMax, O(n) for popMax
popMax may move every value above the largest out and back.
Space Complexity: O(n)
The two stacks, and the buffer during popMax.
Why This Approach Is Not Efficient
With the largest value deep in the stack, popMax moves everything above it out and back. Push 2,000 values from largest to smallest and then popMax until the stack is empty: that digs 1,999,000 values out and back. On the judge it took 916 ms in Python, against 60 ms for the heap below, and on the largest tests it ran out of time in Python. The values above the largest never needed to move. They only needed the largest found and taken out of the middle.
Optimal Approach - A Stack and a Heap of the Same Entries
Intuition
A stack gives the top; a heap of the same values gives the largest. Give every push an id and put the entry in both. popMax takes the heap's top and only marks its id as removed: the entry stays in the stack, and when it reaches the stack's top, it's dropped. pop works the other way round, taking the stack's top and marking its id for the heap. The heap breaks ties by the larger id, so of equal largest values it hands out the newest, the one nearest the top. Each entry goes in once and is dropped once from each side.
Step-by-Step Explanation
Let's trace Example 2 again:
push(2)gets id 0 and goes on the stack and into the heap.push(7)gets id 1 and goes on the stack and into the heap.push(7)gets id 2 and goes on the stack and into the heap.push(3)gets id 3 and goes on the stack and into the heap.popMax(): the heap's top is 7, id 2, the largest value and the newest of equal ones. It comes out of the heap, and in the stack its id is only marked.pop(): 3, id 3, comes off the stack, and its id is marked, since the heap still holds it.top(): id 2, marked, is on top of the stack, so it's dropped first. The top is 7, id 1.popMax(): the heap's top is 7, id 1, the largest value and the newest of equal ones. It comes out of the heap, and in the stack its id is only marked.top(): id 1, marked, is on top of the stack, so it's dropped first. The top is 2, id 0.
A Stack and a Heap of the Same Entries — The stack bottom first and the heap largest first: each side marks what it takes, and the other drops it on reaching its top.
Algorithm
- Keep a stack and a heap of (id, value) entries, the heap ordered by the largest value and then the largest id, and a set of removed ids.
- push gives
xthe next id and adds the entry to both. - pop and top first drop marked entries from the stack's top. pop then takes the top and marks its id; top reads it.
- peekMax and popMax first drop marked entries from the heap's top. popMax then takes the top and marks its id; peekMax reads it.
Code
class MaxStack {
vector<pair<int, int>> stack; // (id, value), the top last
priority_queue<pair<int, int>> heap; // (value, id): the largest value on top, the newest of equal ones
unordered_set<int> removed; // ids taken from one side, still waiting on the other
int nextId = 0;
void dropRemovedFromStack() {
while (removed.count(stack.back().first)) {
removed.erase(stack.back().first);
stack.pop_back();
}
}
void dropRemovedFromHeap() {
while (removed.count(heap.top().second)) {
removed.erase(heap.top().second);
heap.pop();
}
}
public:
MaxStack() {
}
void push(int x) {
stack.push_back({nextId, x});
heap.push({x, nextId});
nextId++;
}
int pop() {
dropRemovedFromStack();
auto [i, x] = stack.back();
stack.pop_back();
removed.insert(i); // the heap still holds it: skip it there later
return x;
}
int top() {
dropRemovedFromStack();
return stack.back().second;
}
int peekMax() {
dropRemovedFromHeap();
return heap.top().first;
}
int popMax() {
dropRemovedFromHeap();
auto [x, i] = heap.top();
heap.pop();
removed.insert(i); // the stack still holds it: skip it there later
return x;
}
};
import heapq
class MaxStack:
def __init__(self):
self.stack = [] # (id, value), the top last
self.heap = [] # (-value, -id): the largest value first, the newest of equal ones
self.removed = set() # ids taken from one side, still waiting on the other
self.next_id = 0
def push(self, x: int) -> None:
self.stack.append((self.next_id, x))
heapq.heappush(self.heap, (-x, -self.next_id))
self.next_id += 1
def pop(self) -> int:
self.drop_removed_from_stack()
i, x = self.stack.pop()
self.removed.add(i) # the heap still holds it: skip it there later
return x
def top(self) -> int:
self.drop_removed_from_stack()
return self.stack[-1][1]
def peekMax(self) -> int:
self.drop_removed_from_heap()
return -self.heap[0][0]
def popMax(self) -> int:
self.drop_removed_from_heap()
x, i = heapq.heappop(self.heap)
self.removed.add(-i) # the stack still holds it: skip it there later
return -x
def drop_removed_from_stack(self):
while self.stack[-1][0] in self.removed:
self.removed.remove(self.stack.pop()[0])
def drop_removed_from_heap(self):
while -self.heap[0][1] in self.removed:
self.removed.remove(-heapq.heappop(self.heap)[1])
class MaxStack {
private final Deque<int[]> stack = new ArrayDeque<>(); // {id, value}, the top first
private final PriorityQueue<int[]> heap = // the largest value on top, the newest of equal ones
new PriorityQueue<>((p, q) -> p[1] != q[1] ? Integer.compare(q[1], p[1]) : Integer.compare(q[0], p[0]));
private final Set<Integer> removed = new HashSet<>(); // ids taken from one side, still waiting on the other
private int nextId = 0;
public MaxStack() {
}
public void push(int x) {
int[] entry = {nextId++, x};
stack.push(entry);
heap.add(entry);
}
public int pop() {
dropRemovedFromStack();
int[] e = stack.pop();
removed.add(e[0]); // the heap still holds it: skip it there later
return e[1];
}
public int top() {
dropRemovedFromStack();
return stack.peek()[1];
}
public int peekMax() {
dropRemovedFromHeap();
return heap.peek()[1];
}
public int popMax() {
dropRemovedFromHeap();
int[] e = heap.poll();
removed.add(e[0]); // the stack still holds it: skip it there later
return e[1];
}
private void dropRemovedFromStack() {
while (removed.contains(stack.peek()[0])) removed.remove(stack.pop()[0]);
}
private void dropRemovedFromHeap() {
while (removed.contains(heap.peek()[0])) removed.remove(heap.poll()[0]);
}
}
// A min-heap in an array: the children of i are at 2i + 1 and 2i + 2, its parent at (i - 1) >> 1.
// less(x, y) says x goes above y: smallest on top unless you pass another.
class MinHeap {
constructor(less = (x, y) => x < y) { this.a = []; this.less = less; }
push(x) {
const a = this.a;
a.push(x);
let i = a.length - 1;
while (i > 0 && this.less(a[i], a[(i - 1) >> 1])) { // sift up while the parent is bigger
const p = (i - 1) >> 1;
[a[i], a[p]] = [a[p], a[i]];
i = p;
}
}
pop() {
const a = this.a;
const top = a[0], last = a.pop();
if (a.length) {
a[0] = last; // the last value takes the root, then sifts down
let i = 0;
while (true) {
const l = 2 * i + 1, r = 2 * i + 2;
let m = i;
if (l < a.length && this.less(a[l], a[m])) m = l;
if (r < a.length && this.less(a[r], a[m])) m = r; // the smaller child, or the bigger ends up above it
if (m === i) break;
[a[i], a[m]] = [a[m], a[i]];
i = m;
}
}
return top;
}
}
var MaxStack = function() {
this.stack = []; // [id, value], the top last
this.heap = new MinHeap((p, q) => p[1] !== q[1] ? p[1] > q[1] : p[0] > q[0]); // the largest value on top, the newest of equal ones
this.removed = new Set(); // ids taken from one side, still waiting on the other
this.nextId = 0;
};
MaxStack.prototype.push = function(x) {
this.stack.push([this.nextId, x]);
this.heap.push([this.nextId, x]);
this.nextId++;
};
MaxStack.prototype.pop = function() {
this.dropRemovedFromStack();
const [i, x] = this.stack.pop();
this.removed.add(i); // the heap still holds it: skip it there later
return x;
};
MaxStack.prototype.top = function() {
this.dropRemovedFromStack();
return this.stack[this.stack.length - 1][1];
};
MaxStack.prototype.peekMax = function() {
this.dropRemovedFromHeap();
return this.heap.a[0][1];
};
MaxStack.prototype.popMax = function() {
this.dropRemovedFromHeap();
const [i, x] = this.heap.pop();
this.removed.add(i); // the stack still holds it: skip it there later
return x;
};
MaxStack.prototype.dropRemovedFromStack = function() {
while (this.removed.has(this.stack[this.stack.length - 1][0])) this.removed.delete(this.stack.pop()[0]);
};
MaxStack.prototype.dropRemovedFromHeap = function() {
while (this.removed.has(this.heap.a[0][0])) this.removed.delete(this.heap.pop()[0]);
};
Complexity Analysis
Time Complexity: O(log n) for push, peekMax and popMax, O(1) for pop and top, amortized
A heap push or pop is O(log n). The marked entries a call drops were each put in once, so over all calls the drops add at most one heap pop per push.
Space Complexity: O(n)
Each pushed entry, in both structures, until it's dropped from both.
Common Mistakes
Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.
Taking the lowest of equal largest values. heapq.heappush(self.heap, (-x, self.next_id))
On Example 1 it returns [null, null, null, null, 5, 5, 5, 5, 5, 1]; the answer is [null, null, null, null, 5, 5, 1, 5, 1, 5]. Of equal largest values, popMax takes the one nearest the top, the newest. A heap that breaks ties by the smaller id hands out the oldest, deep in the stack, and the one on top stays.
pop not telling the heap. i, x = self.stack.pop()
On the calls below it returns [null, null, null, 8, 8]; the answer is [null, null, null, 8, 1].
["MaxStack", "push", "push", "pop", "peekMax"]
[[], [1], [8], [], []]
A value popped from the stack is still in the heap. Unless pop marks its id, peekMax and popMax can answer with a value that's already gone.
top not skipping what popMax took. return self.stack[-1][1]
On Example 1 it returns [null, null, null, null, 5, 5, 5, 5, 1, 5]; the answer is [null, null, null, null, 5, 5, 1, 5, 1, 5]. popMax only marks the value in the stack; it's still there, maybe right on top. top has to drop the marked entries first, as pop does, or it returns a value popMax already took.
Where This Pattern Is Taught
This problem practises keeping two structures over the same entries, joined by an id, where each side skips what the other removed. It's taught in Designing a Data Structure.