Max Stack - Practice Coding Problems

Max Stack - Problem

Linked List Stack Design Doubly-Linked List Ordered Set Hard

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(log n) for each other call.

Input & Output

Example 1 — Basic Operations

$ Input: operations = ["MaxStack","push","push","top","popMax","top"], values = [[],[5],[1],[],[],[]]

› Output: [null,null,null,1,5,1]

💡 Note: MaxStack() creates empty stack. push(5) adds 5. push(1) adds 1 on top. top() returns 1 (top element). popMax() removes and returns 5 (maximum). top() returns 1 (now the only element).

Example 2 — Multiple Max Elements

$ Input: operations = ["MaxStack","push","push","push","peekMax","popMax","top"], values = [[],[5],[1],[5],[],[],[]]

› Output: [null,null,null,null,5,5,1]

💡 Note: After pushing 5,1,5: stack is [5,1,5]. peekMax() returns 5. popMax() removes the top-most 5, leaving [5,1]. top() returns 1.

Example 3 — Pop vs PopMax

$ Input: operations = ["MaxStack","push","push","push","pop","popMax"], values = [[],[3],[2],[1],[],[]]

› Output: [null,null,null,null,1,3]

💡 Note: Stack becomes [3,2,1]. pop() removes top element 1, leaving [3,2]. popMax() removes maximum 3, leaving [2].

Constraints

-10⁷ ≤ x ≤ 10⁷
At most 10⁵ 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.

Visualization

Tap to expand

Understanding the Visualization

Input

Sequence of operations: push, pop, top, peekMax, popMax

Process

Maintain stack order while tracking maximum element

Output

Results of each operation with O(1) top and O(log n) others

Key Takeaway

🎯 Key Insight: Combine doubly-linked list for O(1) stack operations with ordered data structure for O(log n) max operations

Asked in

G Google 45 A Amazon 38 F Facebook 32 M Microsoft 28

The key insight is to combine a doubly-linked list for stack operations with an ordered data structure (TreeMap/OrderedDict) for efficient max operations. The doubly-linked list provides O(1) access to the top element, while the ordered structure enables O(log n) max operations. Best approach uses Doubly-Linked List + TreeMap. Time: O(1) for top, O(log n) for others, Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Array with Linear Search	O(n)	O(n)	Use simple array and search linearly for maximum element
Doubly Linked List + Ordered Set	O(log n)	O(n)	Use doubly-linked list with TreeMap/OrderedDict for O(log n) max operations

Array with Linear Search — Algorithm Steps

Store elements in array with top pointer
For max operations, iterate through array to find maximum
Remove max by shifting elements

Visualization

Tap to expand

Step-by-Step Walkthrough

Push Operations

Elements added to end of array

Find Max

Linear search through all elements

Remove Max

Shift elements to fill gap

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int* stack;
    int top;
    int capacity;
} MaxStack;

MaxStack* maxStackCreate() {
    MaxStack* obj = (MaxStack*)malloc(sizeof(MaxStack));
    obj->capacity = 1000;
    obj->stack = (int*)malloc(obj->capacity * sizeof(int));
    obj->top = -1;
    return obj;
}

void maxStackPush(MaxStack* obj, int val) {
    obj->stack[++obj->top] = val;
}

int maxStackPop(MaxStack* obj) {
    return obj->stack[obj->top--];
}

int maxStackTop(MaxStack* obj) {
    return obj->stack[obj->top];
}

int maxStackPeekMax(MaxStack* obj) {
    int maxVal = obj->stack[0];
    for (int i = 1; i <= obj->top; i++) {
        if (obj->stack[i] > maxVal) {
            maxVal = obj->stack[i];
        }
    }
    return maxVal;
}

int maxStackPopMax(MaxStack* obj) {
    int maxVal = maxStackPeekMax(obj);
    for (int i = obj->top; i >= 0; i--) {
        if (obj->stack[i] == maxVal) {
            int val = obj->stack[i];
            for (int j = i; j < obj->top; j++) {
                obj->stack[j] = obj->stack[j + 1];
            }
            obj->top--;
            return val;
        }
    }
    return -1;
}

int main() {
    printf("[null,null,null,1,null,5]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

peekMax and popMax require linear search through all elements

✓ Linear Growth

Space Complexity

O(n)

Array stores all n elements

⚡ Linearithmic Space

89.0K Views

Medium Frequency

~35 min Avg. Time

1.9K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Array with Linear Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler