Skip to main content
Talentd

Max Stack - Solution & Explanation

HardPremiumFree on FleetCodeLinked ListStackDesignDoubly-Linked List7 min readAsked at: Amazon, Meta, Oracle +7
Practice this problem

Problem Statement

Design a max stack data structure that supports the stack operations and supports finding the stack's maximum element.

Implement the MaxStack class:

  • MaxStack() Initializes the stack object.
  • void push(int x) Pushes element x onto the stack.
  • int pop() Removes the element on top of the stack and returns it.
  • int top() Gets the element on the top of the stack without removing it.
  • int peekMax() Retrieves the maximum element in the stack without removing it.
  • int popMax() Retrieves the maximum element in the stack and removes it. If there is more than one maximum element, only remove the top-most one.

You must come up with a solution that supports O(1) for each top call and O(logn) for each other call.

 

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
MaxStack stk = new MaxStack();
stk.push(5);   // [5] the top of the stack and the maximum number is 5.
stk.push(1);   // [5, 1] the top of the stack is 1, but the maximum is 5.
stk.push(5);   // [5, 1, 5] the top of the stack is 5, which is also the maximum, because it is the top most one.
stk.top();     // return 5, [5, 1, 5] the stack did not change.
stk.popMax();  // return 5, [5, 1] the stack is changed now, and the top is different from the max.
stk.top();     // return 1, [5, 1] the stack did not change.
stk.peekMax(); // return 5, [5, 1] the stack did not change.
stk.pop();     // return 1, [5] the top of the stack and the max element is now 5.
stk.top();     // return 5, [5] the stack did not change.

 

Constraints:

  • -107 <= x <= 107
  • At most 105 calls will be made to push, pop, top, peekMax, and popMax.
  • There will be at least one element in the stack when pop, top, peekMax, or popMax is called.

Approach Overview

Problem Overview: Design a stack that behaves like a normal stack but also supports two extra operations: peekMax() to view the maximum element and popMax() to remove the maximum element. If multiple elements share the maximum value, remove the one closest to the top. The challenge is maintaining both stack order and fast access to the current maximum.

Approach 1: Simple Stack Scan (O(n) popMax)

Use a regular stack to store values. push, pop, and top work in O(1) time. For peekMax(), scan the stack to find the maximum element in O(n) time. For popMax(), repeatedly pop elements into a temporary stack until the maximum is found, remove it, then restore the remaining elements. Time complexity becomes O(n) for both max operations with O(n) auxiliary space during the operation.

Approach 2: Two Stacks (O(n) popMax)

Maintain two stacks: the main stack and a max-tracking stack that stores the maximum value at each level. Each push updates the max stack with max(current, previousMax). peekMax() becomes O(1). However, removing the maximum still requires popping elements until the max appears, then pushing them back. That makes popMax() O(n) time and O(n) temporary space. This improves read performance but not deletion of arbitrary maximum elements.

Approach 3: Doubly Linked List + Ordered Map (O(log n))

The optimal design combines a doubly linked list with an ordered map (like TreeMap or balanced BST). The doubly linked list maintains stack order, enabling push, pop, and top in O(1). The ordered map stores values as keys and a list of node references as values. This lets you locate the largest key quickly.

When pushing, insert a node at the tail of the linked list and store its reference in the ordered map. For peekMax(), retrieve the largest key in the map in O(log n) or O(1) depending on implementation. For popMax(), find the largest value, remove the most recently inserted node from its node list, and unlink that node from the doubly linked list. Both structures stay synchronized.

This design efficiently supports all operations: linked list handles stack order while the ordered structure provides fast maximum lookup. Time complexity is O(log n) for push and popMax(), and O(1) for standard stack operations. Space complexity is O(n). It demonstrates how combining a linked list with an ordered set solves conflicting access patterns.

Recommended for interviews: The doubly linked list + ordered map approach is what interviewers typically expect for this hard design problem. Showing the brute-force stack scan first demonstrates understanding of the constraints, while transitioning to the balanced-map design shows strong data structure design skills.

Solution

Code

PythonJavaC++

Python

Java

C++

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Simple Stack Scanpush/pop O(1), peekMax O(n), popMax O(n)O(n)Good for understanding the problem or quick prototypes
Two Stacks (Stack + Max Stack)push/pop/top O(1), peekMax O(1), popMax O(n)O(n)When frequent max lookups are needed but popMax is rare
Doubly Linked List + Ordered Mappush O(log n), pop O(1), peekMax O(log n), popMax O(log n)O(n)Optimal interview solution supporting fast stack and max operations

Video Solution

Implement A Max Stack - A Stack With A .max() API (Similar To "Min Stack" on LeetCode) • Back To Back SWE • 24,942 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Max Stack easy or hard?
Max Stack is classified as a hard problem because it requires designing a custom data structure rather than applying a standard algorithm. The challenge comes from supporting both stack behavior and efficient maximum element removal at the same time.
Max Stack Python/Java solution
In Python, the structure is often implemented using a doubly linked list plus a sorted dictionary or heap-like structure. In Java, TreeMap is commonly used to maintain ordered keys while storing references to linked list nodes. Both implementations achieve O(log n) push and popMax operations.
How to solve Max Stack in O(n)?
A simpler approach uses a single stack and scans it whenever the maximum element is needed. peekMax iterates through the stack to find the largest value, and popMax temporarily moves elements to another stack until the maximum appears. These operations take O(n) time but keep the implementation straightforward.
What is the best approach for Max Stack?
The most efficient design uses a doubly linked list combined with an ordered map (TreeMap or balanced BST). The linked list maintains stack order while the ordered map keeps values sorted for fast maximum lookup. This allows push in O(log n), pop in O(1), peekMax in O(log n), and popMax in O(log n).
Is Max Stack asked at Google/Amazon/Meta?
Max Stack is a classic system design style data structure problem that appears in interviews at companies like Amazon, Google, and Meta. It tests your ability to combine multiple data structures to satisfy conflicting requirements such as stack order and fast maximum lookup.
What data structure is used in Max Stack?
The optimal solution combines three structures: a stack order maintained by a doubly linked list, an ordered map or TreeMap to keep values sorted, and lists of node references for duplicates. This hybrid design allows efficient removal of the maximum element without scanning the entire stack.
What is the time complexity of Max Stack?
In the optimal implementation using a doubly linked list and ordered map, push and popMax take O(log n) time due to map updates, while pop and top are O(1). peekMax is typically O(log n) depending on how the maximum key is retrieved. Space complexity is O(n) because every element is stored in both structures.

Ready to solve this problem?

Practice Max Stack with our built-in code editor and test cases.

Practice on FleetCode
Previous

Min Stack