Problem 40.10 · Designing Data StructuresHard

Max Stack

PatternCombine Structures to Design BST Ordering

What it teaches: Two views of the same items: a doubly linked list for stack order and a TreeMap for "largest", kept in sync.

Practise it on judges as “Max Stack”.

In plain words

Imagine a stack of exam papers where you sometimes take the top paper, and sometimes pull out the paper with the highest score from wherever it sits in the pile (the one nearest the top if there's a tie).

Build a stack with push(x), pop(), top(), peekMax() (the largest value) and popMax() (remove the largest, the top-most one if tied).

The problem

Design MaxStack supporting push, pop, top, peekMax and popMax. popMax removes the top-most occurrence of the maximum. All calls are valid (the stack is non-empty when needed).

Example 1

Input: push(5), push(1), push(5), top(), popMax(), top(), peekMax(), pop(), top()
Output: 5, 5, 1, 5, 1, 5

Constraints

Up to 10⁵ calls

Pattern clues in the wording

→ Stack order plus "largest" queries
→ Removing from the middle

These clues point to Combine Structures to Design: Pair a hash map (fast lookup) with a list, heap or tree (fast ordering) to meet every operation's time limit.

Stuck? Take one hint at a time

MaxStack · starter

import java.util.*;

class MaxStack {
    public MaxStack() {}
    public void push(int x) {}
    public int pop() { return 0; }
    public int top() { return 0; }
    public int peekMax() { return 0; }
    public int popMax() { return 0; }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#	Input	Expected
1	ops = ["MaxStack","push","push","push","top","popMax","top","peekMax","pop","top"] args = [[],[5],[1],[5],[],[],[],[],[],[]]	[null,null,null,null,5,5,1,5,1,5]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Doubly linked list + TreeMap · O(log n) per call 2. Two stacks (simpler, slower popMax) · O(1) except popMax O(n)

Doubly linked list + TreeMap

Time O(log n) per call Space O(n)

push adds a node at the list's tail and to map[value]. pop removes the tail node and its map entry. popMax takes the last node of map.lastEntry() and unlinks it from the list.

Approach 1

import java.util.*;

class MaxStack {
    private static class Node {
        int val;
        Node prev, next;
        Node(int val) { this.val = val; }
    }

    private final Node head = new Node(0), tail = new Node(0);              // sentinels
    private final TreeMap<Integer, List<Node>> byValue = new TreeMap<>();

    public MaxStack() { head.next = tail; tail.prev = head; }

    public void push(int x) {
        Node n = new Node(x);
        n.prev = tail.prev; n.next = tail;
        tail.prev.next = n; tail.prev = n;
        byValue.computeIfAbsent(x, k -> new ArrayList<>()).add(n);
    }

    public int pop() {
        Node n = tail.prev;
        unlink(n);
        List<Node> same = byValue.get(n.val);
        same.remove(same.size() - 1);                     // the top-most node with this value
        if (same.isEmpty()) byValue.remove(n.val);
        return n.val;
    }

    public int top() { return tail.prev.val; }

    public int peekMax() { return byValue.lastKey(); }

    public int popMax() {
        int max = byValue.lastKey();
        List<Node> same = byValue.get(max);
        Node n = same.remove(same.size() - 1);
        if (same.isEmpty()) byValue.remove(max);
        unlink(n);
        return max;
    }

    private void unlink(Node n) { n.prev.next = n.next; n.next.prev = n.prev; }
}

Verdict: Every operation stays logarithmic.

Two stacks (simpler, slower popMax)

Time O(1) except popMax O(n) Space O(n)

A main stack and a max stack (like Min Stack). popMax pops into a buffer until it finds the max, then pushes the buffer back with push().

▶ Dry run: A stack plus a stack of running maximapush(5), push(1), push(5), top(), popMax(), top(), peekMax(), pop(), top()

stack(stack)

515

maxes(stack)

555

returned(list)

empty

Step 1/5Each push also pushes max(x, current max) onto maxes: 5, then max(1, 5) = 5, then 5.

Approach 2

import java.util.*;

class MaxStack {
    private final Deque<Integer> stack = new ArrayDeque<>(), maxes = new ArrayDeque<>();

    public MaxStack() {}

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

    public int pop() { maxes.pop(); return stack.pop(); }

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

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

    public int popMax() {
        int max = peekMax();
        Deque<Integer> buffer = new ArrayDeque<>();
        while (top() != max) buffer.push(pop());
        pop();
        while (!buffer.isEmpty()) push(buffer.pop());
        return max;
    }
}

Verdict: Fine when popMax is rare.

Before you submit

Edge cases and common mistakes

Test these inputs

Several equal maximums
popMax when the max is on top

Mistakes people make

Removing the bottom-most maximum instead of the top-most.

Interview

Follow-up questions

Why keep a list per value in the TreeMap?

Command Palette