Coding · Stacks
Stack with popMin and popMax
- Reported once
- Medium
- 1 source
One candidate write-up. Treat it as a single data point.
Solve it in the playground, with tests
Design a stack of numbers with push, pop, top, peekMin, peekMax, popMin and popMax, driven as an operation list: run(ops, args) applies each operation with its own argument list and returns one result per operation. pop and top use the most recent surviving push; popMin and popMax remove and return the smallest or largest value, taking the copy nearest the top when values tie; push, and every operation on an empty stack, return null. For push 5, push 1, push 5, peekMax, popMax, top, popMin, pop the results are [null,null,null,5,5,1,1,5]. Up to 100,000 operations are run in order.
Restated in our own words, not a quote from Ola or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
I would ask: what should an operation on an empty stack return? When the smallest value appears several times, which copy does popMin remove, and does that change what top and pop return later? Do the peeks leave the stack alone? How many operations are there, and how large can the values be? And what time is expected per operation?
I would assume null on empty, that popMin and popMax remove the copy nearest the top, that peeks change nothing, and that O(log n) per operation, amortized, is acceptable. I would say plainly that O(1) for every operation is impossible, and explain why.
Brute force
Say the obvious answer and why it is too slow.
Keep a plain array. push appends, pop and top use the last slot. For peekMin or popMin, scan the whole array to find the smallest value and the last position that holds it, then splice that position out, which also shifts the tail. The max versions mirror it. Every min or max operation is O(n), so m operations cost O(m·n).
With 100,000 operations on a stack that has grown to tens of thousands of elements, that is billions of steps. The usual min-stack trick, storing the running minimum beside each element, does not rescue it: removing an element from the middle makes the stored minimums of everything above it wrong.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(n) per operation
- Time
- O(log n) amortized per operation
- Space
- O(n), n = pushes
The pattern is one stack seen through two ordered views. Give every push an id. Keep the ids in an array for stack order, in a min-heap for smallest-first order and in a max-heap for largest-first order. Order the min-heap by value ascending, then newest id first. Order the max-heap by value descending, then newest id first. That ordering is what makes ties take the copy nearest the top.
Removing an element through one view only adds its id to a shared removed set. The other two views still hold the stale id, and they discard it lazily: before each operation, pop dead ids off the top of the stack array and off the front of both heaps. After that cleanup, the front of each structure is a live element, so top, peekMin and peekMax are plain reads, and pop, popMin and popMax remove and mark the front.
Why it is correct: an id is marked only when its element is truly gone, so every live element sits in all three structures, and cleanup removes only dead ones. Each id enters each structure once and leaves it once, so total heap work is O(log n) per push plus O(log n) per removal, amortized. Dead ids stay in memory until they are purged, so space is proportional to the number of pushes, not to the live size.
About O(1): if push and popMin were both O(1), pushing n numbers and popping the minimum n times would sort in O(n) comparisons, which no comparison-based method can do. So O(log n) is the right target; only a bounded value range allows buckets. Heaps with lazy deletion are the same trick Dijkstra uses for stale entries.
Walk it through
A dry run on the example, step by step.
| Op | Live stack | Min | Max | Returns |
|---|---|---|---|---|
| push 5 | [5a] | 5 | 5 | null |
| push 1 | [5a, 1] | 1 | 5 | null |
| push 5 | [5a, 1, 5b] | 1 | 5 | null |
| peekMax | [5a, 1, 5b] | 1 | 5 | 5 |
| popMax | [5a, 1] | 1 | 5 | 5 (removes 5b) |
| top | [5a, 1] | 1 | 5 | 1 |
| popMin | [5a] | 5 | 5 | 1 |
| pop | [] | - | - | 5 |
Use push 5, push 1, push 5, peekMax, popMax, top, popMin, pop. I label the two fives 5a and 5b so you can tell them apart in the trace table.
After the three pushes the stack is [5a, 1, 5b] with min 1 and max 5. peekMax returns 5 and changes nothing. popMax has two fives to choose from and removes 5b, the one nearest the top, so the stack becomes [5a, 1]. top now returns 1; had popMax removed 5a, top would wrongly return 5. popMin removes 1, leaving [5a]. pop returns 5. The results are null, null, null, 5, 5, 1, 1, 5.
The code
Runnable JavaScript, checked against test cases.
const before = (a, b) => (a[0] - b[0] || a[1] - b[1]) < 0;
function heapPush(heap, item) {
heap.push(item);
for (let i = heap.length - 1; i > 0; ) {
const parent = (i - 1) >> 1;
if (!before(heap[i], heap[parent])) break;
[heap[i], heap[parent]] = [heap[parent], heap[i]];
i = parent;
}
}
function heapPop(heap) {
const top = heap[0];
const last = heap.pop();
if (heap.length === 0) return top;
heap[0] = last;
for (let i = 0, child = 1; child < heap.length; child = 2 * i + 1) {
if (child + 1 < heap.length && before(heap[child + 1], heap[child])) child++;
if (!before(heap[child], heap[i])) break;
[heap[i], heap[child]] = [heap[child], heap[i]];
i = child;
}
return top;
}
function run(ops, args) {
const values = [], stack = [], minHeap = [], maxHeap = [], removed = new Set();
const take = (id) => (removed.add(id), values[id]);
const actions = {
push: (value) => {
stack.push(values.length);
heapPush(minHeap, [value, -values.length]);
heapPush(maxHeap, [-value, -values.length]);
values.push(value);
return null;
},
top: () => values[stack[stack.length - 1]],
pop: () => take(stack.pop()),
peekMin: () => minHeap[0][0],
peekMax: () => -maxHeap[0][0],
popMin: () => take(-heapPop(minHeap)[1]),
popMax: () => take(-heapPop(maxHeap)[1]),
};
return ops.map((op, i) => {
while (stack.length > 0 && removed.has(stack[stack.length - 1])) stack.pop();
for (const heap of [minHeap, maxHeap]) {
while (heap.length > 0 && removed.has(-heap[0][1])) heapPop(heap);
}
return op !== "push" && stack.length === 0 ? null : actions[op](...args[i]);
});
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
Any operation on an empty stack returns null: after cleanup, an empty stack array means no live element exists, so the code checks it once before dispatching. The same check covers a stack emptied by a mix of pops and popMin or popMax calls.
Equal values are handled by the id tie-break, so a stack of identical numbers still removes the top copy first. A popMin from the middle leaves a dead id in the stack array; it is skipped the next time it reaches the top. Zero and negative values work: the max-heap stores the negated value, and peekMax negates it back. Pushing after the stack has become empty simply reuses the structures, and ids keep growing so they never clash.
Follow-ups to expect
Where the interviewer pushes next.
- How would you make every operation worst-case O(log n) rather than amortized, using a doubly linked list and a balanced ordered map?
- What changes if popMin must take the oldest copy of the minimum instead of the newest?
- If values were small integers from 0 to 100, could you make every operation O(1)?
- How would you also support reading the median of the surviving elements?
- Why does lazy deletion keep the total work bounded even though stale entries linger inside the heaps?
Where candidates slip
The mistakes this problem punishes.
The biggest slip is promising O(1) for everything, which contradicts the sorting lower bound. The next is removing from the heaps in popMin but forgetting that the stack array still holds the id, so a later pop returns a value that is already gone.
Others: not purging stale entries before a peek, so peekMin returns a removed value; keying the removed set by value instead of by id, which breaks as soon as duplicates appear; ordering the heaps by value alone, so tie-breaks are arbitrary and top changes unpredictably afterwards; and forgetting that an empty heap read crashes. Some also pick a Map of counts and lose the stack order entirely.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.