Max Stack

Q: What is the best time complexity for Max Stack?

Optimal (stack + max-heap with lazy deletion) runs in O(log n) amortized per operation time and O(n) extra space. Heap insertions and removals cost O(log n); each element is discarded lazily at most once from each structure, so the cleanup is paid for by its push.

Q: Which pattern does Max Stack use?

It is a design data structures problem that uses the stack pattern. Other problems with the same pattern: Min Stack, Design a Stack With Increment Operation, Maximum Frequency Stack.

Q: Is there a brute force solution for Max Stack?

Yes. Brute force (scan the list) takes O(1) push/pop/top, O(n) peekMax/popMax time and O(n) space. Store everything in a list whose end is the top of the stack.

Q: Which edge cases should I test for Max Stack?

The maximum appears several times: popMax must remove the copy nearest the top; The maximum is the top element, so popMax behaves exactly like pop; The maximum sits at the very bottom of the stack; Negative values only.

Hard Design Data Structures Stack Original on LeetCode

Reported atLinkedIn Salesforce

Max Stack is a hard design data structures problem solved with the stack pattern. The best approach, optimal (stack + max-heap with lazy deletion), runs in O(log n) amortized per operation time and O(n) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (scan the list) up.

Problem

Design a class MaxStack that behaves like a normal stack but can also find and remove its largest element. MaxStack() creates an empty stack.

push(int x) puts x on top. pop() removes the top element and returns it, and top() returns it without removing it. peekMax() returns the largest value currently in the stack. popMax() removes the largest value and returns it; if that value occurs more than once, only the copy closest to the top is removed.

Try to make top O(1) and every other operation O(log n).

Examples

Example 1

Input: MaxStack(), push(4), push(9), push(2), push(9), top(), popMax(), peekMax(), pop(), top(), peekMax()
Output: 9, 9, 9, 2, 9, 9
Why: Two copies of 9 are on the stack; popMax removes the upper one, so the lower 9 is still the maximum after 2 is popped.

Example 2

Input: MaxStack(), push(-3), push(6), push(1), popMax(), top(), popMax(), popMax()
Output: 6, 1, 1, -3
Why: Removing 6 from the middle leaves 1 on top, and 1 then becomes the largest value.

Constraints

-10^7 <= x <= 10^7
At most 10^5 calls in total to push, pop, top, peekMax and popMax.
pop, top, peekMax and popMax are only called when the stack is not empty.
Aim for O(1) top and O(log n) for every other operation.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00

Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

Approach	Time	Space
Brute force (scan the list)	`O(1) push/pop/top, O(n) peekMax/popMax`	`O(n)`
Better (value stack + running-max stack)	`O(1) push/pop/top/peekMax, O(n) popMax`	`O(n)`
Optimal (stack + max-heap with lazy deletion)	`O(log n) amortized per operation`	`O(n)`

1Brute force (scan the list)

TimeO(1) push/pop/top, O(n) peekMax/popMaxpeekMax and popMax look at every element; removing from the middle also shifts the elements after it.

SpaceO(n)The list holds all n elements.

Store everything in a list whose end is the top of the stack. push, pop and top work on the end. peekMax and popMax scan the whole list; popMax scans from the top down so it finds the topmost copy of the maximum first.

push(x): append x; pop(): remove and return the last element; top(): return the last element.
peekMax(): return the largest value in the list.
popMax(): walk from the end to the start, remember the index of the first occurrence of the largest value seen, remove that index and return its value.

class MaxStack {
    private final List<Integer> list = new ArrayList<>();

    public void push(int x) { list.add(x); }

    public int pop() { return list.remove(list.size() - 1); }

    public int top() { return list.get(list.size() - 1); }

    public int peekMax() {
        int best = Integer.MIN_VALUE;
        for (int x : list) best = Math.max(best, x);
        return best;
    }

    public int popMax() {
        int idx = list.size() - 1;
        for (int i = list.size() - 1; i >= 0; i--) {
            if (list.get(i) > list.get(idx)) idx = i;
        }
        return list.remove(idx);
    }
}

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

    def push(self, x: int) -> None:
        self.items.append(x)

    def pop(self) -> int:
        return self.items.pop()

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

    def peekMax(self) -> int:
        return max(self.items)

    def popMax(self) -> int:
        idx = len(self.items) - 1
        for i in range(len(self.items) - 1, -1, -1):
            if self.items[i] > self.items[idx]:
                idx = i
        return self.items.pop(idx)

class MaxStack {
    vector<int> items;

public:
    MaxStack() {}

    void push(int x) { items.push_back(x); }

    int pop() {
        int v = items.back();
        items.pop_back();
        return v;
    }

    int top() { return items.back(); }

    int peekMax() { return *max_element(items.begin(), items.end()); }

    int popMax() {
        int idx = (int)items.size() - 1;
        for (int i = (int)items.size() - 1; i >= 0; i--) {
            if (items[i] > items[idx]) idx = i;
        }
        int v = items[idx];
        items.erase(items.begin() + idx);
        return v;
    }
};

class MaxStack {
    constructor() {
        this.items = [];
    }

    push(x) { this.items.push(x); }

    pop() { return this.items.pop(); }

    top() { return this.items[this.items.length - 1]; }

    peekMax() {
        let best = -Infinity;
        for (const x of this.items) best = Math.max(best, x);
        return best;
    }

    popMax() {
        let idx = this.items.length - 1;
        for (let i = this.items.length - 1; i >= 0; i--) {
            if (this.items[i] > this.items[idx]) idx = i;
        }
        return this.items.splice(idx, 1)[0];
    }
}

2Better (value stack + running-max stack)

TimeO(1) push/pop/top/peekMax, O(n) popMaxpopMax may move every element above the maximum into the buffer and back.

SpaceO(n)Two stacks of n entries plus a buffer of up to n entries.

Next to the normal stack keep a second stack where each slot holds the maximum of everything at or below that position. peekMax is then just the top of the second stack. For popMax, pop elements into a buffer until the maximum is on top, remove it, and push the buffered elements back with the normal push so the running maxima are rebuilt.

push(x): push x on st; push max(x, maxSt top) on maxSt (or x if empty).
pop(): pop both stacks and return the value from st. top(): peek st. peekMax(): peek maxSt.
popMax(): m = peekMax(); pop into a buffer until the top of st equals m; pop m.
Push the buffered values back in reverse order of removal and return m.

class MaxStack {
    private final Deque<Integer> st = new ArrayDeque<>();
    private final Deque<Integer> maxSt = new ArrayDeque<>();

    public void push(int x) {
        st.push(x);
        maxSt.push(maxSt.isEmpty() ? x : Math.max(x, maxSt.peek()));
    }

    public int pop() {
        maxSt.pop();
        return st.pop();
    }

    public int top() { return st.peek(); }

    public int peekMax() { return maxSt.peek(); }

    public int popMax() {
        int m = maxSt.peek();
        Deque<Integer> buffer = new ArrayDeque<>();
        while (st.peek() != m) buffer.push(pop());
        pop();
        while (!buffer.isEmpty()) push(buffer.pop());
        return m;
    }
}

class MaxStack:
    def __init__(self):
        self.st = []
        self.max_st = []

    def push(self, x: int) -> None:
        self.st.append(x)
        self.max_st.append(x if not self.max_st else max(x, self.max_st[-1]))

    def pop(self) -> int:
        self.max_st.pop()
        return self.st.pop()

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

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

    def popMax(self) -> int:
        m = self.max_st[-1]
        buffer = []
        while self.st[-1] != m:
            buffer.append(self.pop())
        self.pop()
        while buffer:
            self.push(buffer.pop())
        return m

class MaxStack {
    vector<int> st, maxSt;

public:
    MaxStack() {}

    void push(int x) {
        st.push_back(x);
        maxSt.push_back(maxSt.empty() ? x : max(x, maxSt.back()));
    }

    int pop() {
        maxSt.pop_back();
        int v = st.back();
        st.pop_back();
        return v;
    }

    int top() { return st.back(); }

    int peekMax() { return maxSt.back(); }

    int popMax() {
        int m = maxSt.back();
        vector<int> buffer;
        while (st.back() != m) buffer.push_back(pop());
        pop();
        while (!buffer.empty()) {
            push(buffer.back());
            buffer.pop_back();
        }
        return m;
    }
};

class MaxStack {
    constructor() {
        this.st = [];
        this.maxSt = [];
    }

    push(x) {
        this.st.push(x);
        const n = this.maxSt.length;
        this.maxSt.push(n === 0 ? x : Math.max(x, this.maxSt[n - 1]));
    }

    pop() {
        this.maxSt.pop();
        return this.st.pop();
    }

    top() { return this.st[this.st.length - 1]; }

    peekMax() { return this.maxSt[this.maxSt.length - 1]; }

    popMax() {
        const m = this.peekMax();
        const buffer = [];
        while (this.top() !== m) buffer.push(this.pop());
        this.pop();
        while (buffer.length > 0) this.push(buffer.pop());
        return m;
    }
}

3Optimal (stack + max-heap with lazy deletion)

TimeO(log n) amortized per operationHeap insertions and removals cost O(log n); each element is discarded lazily at most once from each structure, so the cleanup is paid for by its push.

SpaceO(n)The stack, the heap and the removed set each hold at most n entries.

Tag every pushed value with a unique, increasing id. Keep the pairs in a stack (for pop/top) and in a max-heap ordered by value, then by id, so among equal values the most recently pushed one wins. When one structure removes an element, put its id in a removed set instead of searching for it in the other structure. Before reading the top of either structure, throw away entries whose id is in removed.

push(x): create {x, id++} and add it to both the stack and the heap.
Before any read of the stack top, pop entries whose id is in removed (and drop the id from the set). Do the same for the heap top.
pop(): clean the stack, pop its top, add the id to removed, return the value. top(): clean the stack and peek.
popMax(): clean the heap, poll its top, add the id to removed, return the value. peekMax(): clean the heap and peek.

class MaxStack {
    private final Deque<int[]> stack = new ArrayDeque<>();
    private final PriorityQueue<int[]> heap = new PriorityQueue<>(
            (a, b) -> a[0] != b[0] ? Integer.compare(b[0], a[0]) : Integer.compare(b[1], a[1]));
    private final Set<Integer> removed = new HashSet<>();
    private int nextId = 0;

    public void push(int x) {
        int[] e = { x, nextId++ };
        stack.push(e);
        heap.add(e);
    }

    private void cleanStack() {
        while (removed.contains(stack.peek()[1])) removed.remove(stack.pop()[1]);
    }

    private void cleanHeap() {
        while (removed.contains(heap.peek()[1])) removed.remove(heap.poll()[1]);
    }

    public int pop() {
        cleanStack();
        int[] e = stack.pop();
        removed.add(e[1]);
        return e[0];
    }

    public int top() {
        cleanStack();
        return stack.peek()[0];
    }

    public int peekMax() {
        cleanHeap();
        return heap.peek()[0];
    }

    public int popMax() {
        cleanHeap();
        int[] e = heap.poll();
        removed.add(e[1]);
        return e[0];
    }
}

class MaxStack:
    def __init__(self):
        self.stack = []  # (value, id)
        self.heap = []  # (-value, -id) so the largest value, then newest id, is on top
        self.removed = set()
        self.next_id = 0

    def push(self, x: int) -> None:
        self.stack.append((x, self.next_id))
        heapq.heappush(self.heap, (-x, -self.next_id))
        self.next_id += 1

    def _clean_stack(self) -> None:
        while self.stack[-1][1] in self.removed:
            self.removed.discard(self.stack.pop()[1])

    def _clean_heap(self) -> None:
        while -self.heap[0][1] in self.removed:
            self.removed.discard(-heapq.heappop(self.heap)[1])

    def pop(self) -> int:
        self._clean_stack()
        x, i = self.stack.pop()
        self.removed.add(i)
        return x

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

    def peekMax(self) -> int:
        self._clean_heap()
        return -self.heap[0][0]

    def popMax(self) -> int:
        self._clean_heap()
        x, i = heapq.heappop(self.heap)
        self.removed.add(-i)
        return -x

class MaxStack {
    vector<pair<int, int>> st;           // (value, id)
    priority_queue<pair<int, int>> heap; // max by value, then by id
    unordered_set<int> removed;
    int nextId = 0;

    void cleanStack() {
        while (removed.count(st.back().second)) {
            removed.erase(st.back().second);
            st.pop_back();
        }
    }

    void cleanHeap() {
        while (removed.count(heap.top().second)) {
            removed.erase(heap.top().second);
            heap.pop();
        }
    }

public:
    MaxStack() {}

    void push(int x) {
        st.push_back({x, nextId});
        heap.push({x, nextId});
        nextId++;
    }

    int pop() {
        cleanStack();
        auto e = st.back();
        st.pop_back();
        removed.insert(e.second);
        return e.first;
    }

    int top() {
        cleanStack();
        return st.back().first;
    }

    int peekMax() {
        cleanHeap();
        return heap.top().first;
    }

    int popMax() {
        cleanHeap();
        auto e = heap.top();
        heap.pop();
        removed.insert(e.second);
        return e.first;
    }
};

class MaxStack {
    constructor() {
        this.stack = []; // [value, id]
        this.heap = []; // binary max-heap of [value, id]
        this.removed = new Set();
        this.nextId = 0;
    }

    higher(a, b) { return a[0] !== b[0] ? a[0] > b[0] : a[1] > b[1]; }

    heapPush(e) {
        const h = this.heap;
        h.push(e);
        let i = h.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (!this.higher(h[i], h[p])) break;
            [h[i], h[p]] = [h[p], h[i]];
            i = p;
        }
    }

    heapPop() {
        const h = this.heap;
        const top = h[0];
        const last = h.pop();
        if (h.length > 0) {
            h[0] = last;
            let i = 0;
            while (true) {
                const l = 2 * i + 1, r = l + 1;
                let m = i;
                if (l < h.length && this.higher(h[l], h[m])) m = l;
                if (r < h.length && this.higher(h[r], h[m])) m = r;
                if (m === i) break;
                [h[i], h[m]] = [h[m], h[i]];
                i = m;
            }
        }
        return top;
    }

    push(x) {
        const e = [x, this.nextId++];
        this.stack.push(e);
        this.heapPush(e);
    }

    cleanStack() {
        while (this.removed.has(this.stack[this.stack.length - 1][1])) {
            this.removed.delete(this.stack.pop()[1]);
        }
    }

    cleanHeap() {
        while (this.removed.has(this.heap[0][1])) {
            this.removed.delete(this.heapPop()[1]);
        }
    }

    pop() {
        this.cleanStack();
        const e = this.stack.pop();
        this.removed.add(e[1]);
        return e[0];
    }

    top() {
        this.cleanStack();
        return this.stack[this.stack.length - 1][0];
    }

    peekMax() {
        this.cleanHeap();
        return this.heap[0][0];
    }

    popMax() {
        this.cleanHeap();
        const e = this.heapPop();
        this.removed.add(e[1]);
        return e[0];
    }
}

Edge cases to test

The maximum appears several times: popMax must remove the copy nearest the top
The maximum is the top element, so popMax behaves exactly like pop
The maximum sits at the very bottom of the stack
Negative values only

Hints

Hint 1

A second stack holding the running maximum answers peekMax in O(1). What goes wrong for popMax?

Hint 2

Removing from the middle is the hard part. Instead of physically removing an element from both structures, could you just mark it as gone?

Hint 3

Give every pushed element a unique increasing id. Keep the elements in a stack and in a max-heap ordered by (value, id). When one structure removes an element, record its id; the other structure skips recorded ids when they reach its top.

FAQ

What is the best time complexity for Max Stack?

Optimal (stack + max-heap with lazy deletion) runs in O(log n) amortized per operation time and O(n) extra space. Heap insertions and removals cost O(log n); each element is discarded lazily at most once from each structure, so the cleanup is paid for by its push.

Which pattern does Max Stack use?

It is a design data structures problem that uses the stack pattern. Other problems with the same pattern: Min Stack, Design a Stack With Increment Operation, Maximum Frequency Stack.

Is there a brute force solution for Max Stack?

Yes. Brute force (scan the list) takes O(1) push/pop/top, O(n) peekMax/popMax time and O(n) space. Store everything in a list whose end is the top of the stack.

Which edge cases should I test for Max Stack?

The maximum appears several times: popMax must remove the copy nearest the top; The maximum is the top element, so popMax behaves exactly like pop; The maximum sits at the very bottom of the stack; Negative values only.