Domain 1EasyCORE

Max Stack

We need to design a `MaxStack` data structure that supports standard stack operations (`push`, `pop`, `top`) along with additional operations to find the maximum element in the stack (`peekMax`) and remove the maximum element (`popMax`). The stack should support these operations efficiently.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Design

716. Max Stack

Model: qwen2.5-coder:14b
Topics: Design
FAANG asked: 1
Acceptance rate: 43.1%


Problem Breakdown

We need to design a MaxStack data structure that supports standard stack operations (push, pop, top) along with additional operations to find the maximum element in the stack (peekMax) and remove the maximum element (popMax). The stack should support these operations efficiently.

Inputs:

  • push(int x): Adds an integer x to the top of the stack.
  • pop(): Removes and returns the top element of the stack.
  • top(): Returns the top element without removing it.
  • peekMax(): Returns the maximum element in the stack without removing it.
  • popMax(): Removes and returns the maximum element from the stack. If there are multiple maximum elements, only the top-most one should be removed.

Outputs:

  • The operations return specific values as described above.

Implicit Constraints/Edge Cases:

  • The stack can contain negative numbers.
  • There will always be at least one element in the stack when pop, top, peekMax, or popMax is called.
  • At most 10,000 calls will be made to these operations.

Intuition

A brute-force approach would involve maintaining a single list and performing linear scans for peekMax and popMax. This would result in O(n) time complexity for these operations, which is inefficient given the constraints.

The key insight is to use two stacks: one for regular stack operations and another to keep track of the maximum elements. By doing this, we can achieve O(1) time complexity for top and O(log n) for other operations.

Approach

  1. Data Structures:

    • Use a primary stack (stack) to store all elements.
    • Use an auxiliary stack (max_stack) to keep track of the maximum elements. The top of this stack will always be the current maximum element in the stack.
  2. Operations:

    • push(int x): Push x onto the primary stack. If x is greater than or equal to the current maximum (top of max_stack), push it onto max_stack.
    • pop(): Pop and return the top element from the primary stack. If this element is equal to the top of max_stack, pop it from max_stack as well.
    • top(): Return the top element of the primary stack without removing it.
    • peekMax(): Return the top element of max_stack, which represents the current maximum in the primary stack.
    • popMax(): To remove the maximum element, temporarily pop elements from the primary stack and push them onto a temporary stack until the maximum is found. Then, pop the maximum element. Reinsert all elements from the temporary stack back into the primary stack and update max_stack accordingly.

Complexity Analysis

  • Time Complexity:
    • push, pop, top: O(1)
    • peekMax: O(1)
    • popMax: O(n) in the worst case, but amortized over multiple operations, it can be considered efficient due to the reinsertion of elements.
  • Space Complexity: O(n), where n is the number of elements pushed onto the stack. This is due to the storage required for both stacks.

Solution

class MaxStack:
    def __init__(self):
        self.stack = []
        self.max_stack = []

    def push(self, x: int) -> None:
        self.stack.append(x)
        if not self.max_stack or x >= self.max_stack[-1]:
            self.max_stack.append(x)

    def pop(self) -> int:
        val = self.stack.pop()
        if val == self.max_stack[-1]:
            self.max_stack.pop()
        return val

    def top(self) -> int:
        return self.stack[-1]

    def peekMax(self) -> int:
        return self.max_stack[-1]

    def popMax(self) -> int:
        max_val = self.max_stack[-1]
        temp = []
        while self.stack[-1] != max_val:
            temp.append(self.stack.pop())
        
        self.stack.pop()  # Remove the max element
        self.max_stack.pop()
        
        # Reinsert elements from temp back into stack and update max_stack
        for x in reversed(temp):
            self.push(x)
        
        return max_val

Edge Cases Handled

  • Negative Numbers: The solution correctly handles negative numbers as it compares values without any assumptions.
  • Multiple Maximums: When multiple maximum elements exist, popMax removes only the top-most one by design.
  • Empty Stack Operations: The problem constraints ensure that operations like pop, top, peekMax, and popMax are never called on an empty stack, so these cases do not need to be explicitly handled.