Max Stack

HardStackheap

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Design a stack that, in addition to the usual operations, can report and remove its **maximum** element. - MaxStack() creates an empty stack. - push(x) pushes x onto the top. - pop() removes and returns the top element. - top() returns the top element without removing it. - peekMax() returns the largest element without removing it. - popMax() removes and returns the largest element. If the maximum occurs more than once, remove the copy **closest to the top**. pop, top, peekMax, and popMax are only called on a non-empty stack. Aim for O(log n) per operation (O(1) for top).

Examples

Input: ["MaxStack","push","push","push","top","popMax","top","peekMax","pop","top"] [[],[3],[1],[3],[],[],[],[],[],[]]
Output: [null,null,null,null,3,3,1,3,1,3]
The stack is 3, 1, 3 (top last). `popMax` removes the top-most 3, leaving 3, 1. Then `pop` removes 1 and the remaining 3 is on top.
Input: ["MaxStack","push","push","push","popMax","top","pop","peekMax","popMax"] [[],[2],[7],[4],[],[],[],[],[]]
Output: [null,null,null,null,7,4,4,2,2]
Removing the maximum 7 from the middle keeps 4 on top. After popping 4, only 2 is left.

Constraints

  • `-10^7 <= x <= 10^7`
  • At most 10^5 calls in total.
  • `pop`, `top`, `peekMax`, and `popMax` are never called on an empty stack.

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More heap problems