716. Max Stack

HardStackDesignLinked ListDoubly-Linked ListOrdered Set

Problem Description

The problem asks us to design a customized stack structure, which is a common Last-In-First-Out (LIFO) data structure with an added capability of retrieving and removing the maximum element it contains. This stack should support the following operations:

push(x): Add an element x to the top of the stack.
pop(): Remove the element at the top of the stack and return it.
top(): Return the element at the top of the stack without removing it.
peekMax(): Retrieve the maximum element in the stack without removing it.
popMax(): Retrieve the maximum element in the stack and remove it. If there are multiple instances of the maximum element, only the top-most one should be removed.

The challenge lies in designing these operations to be time efficient, specifically requiring the top call to be O(1) and all other calls to be O(log n) complexity.

Intuition

To arrive at the solution, we must combine the simplicity of accessing the top element in O(1) time via a standard stack and the organized structure of a sorted set that allows O(log n) retrieval and removal of the maximum element.

The intuition behind the solution is to maintain not only a normal stack for fast push and pop operations but also to maintain a sorted list of elements that can provide quick access to the maximum element.

Here is the step-by-step intuition:

Dual Data Structures: Utilize two data structures: a doubly linked list to act as the stack (providing O(1) top operation and quick addition/removal at the end) and a sorted list to keep track of the elements in sorted order (allowing O(log n) complexity for peekMax and popMax).
Doubly Linked List: The stack needs to consist of nodes that keep track of their previous and next elements (hence a doubly linked list). Each node is a simple class that holds an integer value and pointers referring to the preceding and succeeding nodes.
SortedList: The sorted list from the sortedcontainers module in Python which handles insertion, removal, and retrieval in logarithmic time complexity. Each node from the doubly linked list is also stored in this sorted list to facilitate ordered access.
Maintain References: The nodes stored in the sorted list are the same as those in the doubly linked list. This means any changes such as removal from one structure must be mirrored in the other without searching as we have direct references to the nodes.
Synchronized Operations: When an element is pushed, it is added to both the doubly linked list (on top) and the sorted list (in order). When popping the top element or the maximum element, it is careful to remove the element from both structures to maintain consistency.

The result of this approach is a MaxStack which provides efficient O(1) or O(log n) operations for all the required methods, as requested by the problem description.

Learn more about Stack and Linked List patterns.

Solution Approach

The implementation of the MaxStack uses a combination of a doubly linked list and a sorted list to keep track of the elements in the stack and their order, respectively. Below is a walk-through of the key components of the implementation:

Doubly Linked List

The custom Node class is defined to hold individual elements, with each node knowing its value as well as its prev (previous) and next (next) nodes. This supports bidirectional traversal.

The DoubleLinkedList class is then defined to act as our stack, with methods to append (add a new node at the end), remove (detach a given node from the list), pop (remove the last element), and peek (look at the last element without removing it).

Sorted List

The sorted list imported as SortedList is used to maintain a sorted sequence of the elements contained in the doubly linked list. This is possible due to the list being ordered. Each node added to the doubly linked list is added to the sorted list as well, sorted by the val (value) of the nodes.

MaxStack Class

The MaxStack class combines the above structures. It has an instantiation of the DoubleLinkedList to act as the main stack and a SortedList to keep track of the nodes in a sorted manner.

`push(x: int)`

When a new value is pushed onto the stack, a new node is created in the doubly linked list and also added to the sorted list. The sorted list handles reordering.

`pop() -> int`

To pop an element, the last node is removed from the doubly linked list, and then the same node is removed from the sorted list, ensuring consistency between the two data structures.

`top() -> int`

The top operation becomes quite simple as we just return the value of the last node in the doubly linked list, which is always at the end and therefore an O(1) operation.

`peekMax() -> int`

Peeking at the maximum element is also straightforward as we can access the last element of the sorted list (which, by definition, is the largest), returning its value.

`popMax() -> int`

To pop the maximum element, we first remove it from the sorted list (which is the last element of the list). Knowing the node that needs to be popped is beneficial since we can directly access it and remove it from the doubly linked list.

Synchronization of Data Structures

It’s critical that the doubly linked list and the sorted list remain synchronized. Any node operations (insertion and deletion) are performed in both structures simultaneously.

By utilizing the doubly linked list for the stack's basic functionality and the sorted list for efficient access to the maximum elements, the solution fulfills the operation time complexity requirements set out in the problem description.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with a small example. Assume we're operating on an initially empty MaxStack.

First, we push the following elements: 5, 1, and 10.

push(5)

Create a new node with the value 5 and append it to the doubly linked list.
Insert the node with value 5 into the sorted list, which is now [5].

push(1)

Create a new node with the value 1 and append it to the doubly linked list.
Insert the node with value 1 into the sorted list, which is now [1, 5].

push(10)

Create a new node with the value 10 and append it to the doubly linked list.
Insert the node with value 10 into the sorted list, which reorders to [1, 5, 10].

Now, if we want to perform different operations like pop, top, peekMax, and popMax, here's how we would proceed:

pop()

The last element in the doubly linked list, 10, is removed.
We find the same node in the sorted list and remove it, resulting in [1, 5].

top()

Simply return the current top element of the doubly linked list, which is 1.

peekMax()

Access the last element of the sorted list, and return its value, which is 5.

popMax()

Remove the last element of the sorted list, which is the node with the value 5.
Remove the same node from the doubly linked list.

The doubly linked list manages stack operations efficiently, while the sorted list keeps track of element order, allowing us to maintain the stack with our desired time complexities.

Solution Implementation

1from sortedcontainers import SortedList
2from typing import Optional
3
4class Node:
5    def __init__(self, val: int = 0):
6        self.val = val  # Value of the node
7        self.prev: Optional['Node'] = None  # Link to the previous node
8        self.next: Optional['Node'] = None  # Link to the next node
9
10
11class DoubleLinkedList:
12    def __init__(self):
13        self.head = Node()  # Sentinel head node of the double linked list
14        self.tail = Node()  # Sentinel tail node of the double linked list
15        self.head.next = self.tail  # Connect head to tail
16        self.tail.prev = self.head  # Connect tail to head
17
18    def append(self, val: int) -> Node:
19        """
20        Append a new node with value val at the end of the list
21        :param val: Value to append
22        :return: Node that was appended
23        """
24        # Create new node
25        node = Node(val)
26        # Link it with the last element
27        node.next = self.tail
28        node.prev = self.tail.prev
29        # Link the last element with the new node
30        self.tail.prev.next = node
31        self.tail.prev = node
32        return node
33
34    @staticmethod
35    def remove_node(node: Node) -> None:
36        """
37        Remove a node from the list
38        :param node: Node to be removed
39        :return: None
40        """
41        # Re-link the previous and next nodes to each other
42        node.prev.next = node.next
43        node.next.prev = node.prev
44
45    def pop(self) -> Node:
46        """
47        Pop the last element from the list
48        :return: Node that was popped
49        """
50        # Use the remove_node static method to remove the last element
51        return self.remove_node(self.tail.prev)
52
53    def peek(self) -> int:
54        """
55        Peek the last element's value from the list
56        :return: Value of last node
57        """
58        return self.tail.prev.val
59
60
61class MaxStack:
62    def __init__(self):
63        self.stack = DoubleLinkedList()  # The main stack as a double linked list
64        self.sorted_nodes = SortedList(key=lambda x: x.val)  # Sorted keys to track max values efficiently
65
66    def push(self, x: int) -> None:
67        """
68        Push an element onto the stack
69        :param x: Value to push onto the stack
70        :return: None
71        """
72        # Append value to stack and add the node to sorted list for max retrieval
73        node = self.stack.append(x)
74        self.sorted_nodes.add(node)
75
76    def pop(self) -> int:
77        """
78        Pop the top element from the stack
79        :return: Value of removed element
80        """
81        # Pop from stack and remove corresponding node from sorted list
82        node = self.stack.pop()
83        self.sorted_nodes.remove(node)
84        return node.val
85
86    def top(self) -> int:
87        """
88        Get the top element of the stack
89        :return: Value of top element
90        """
91        return self.stack.peek()
92
93    def peekMax(self) -> int:
94        """
95        Retrieve the maximum value in the stack
96        :return: Maximum value
97        """
98        # Last element of sorted_nodes has the max value
99        return self.sorted_nodes[-1].val
100
101    def popMax(self) -> int:
102        """
103        Pop the maximum value from the stack
104        :return: Maximum value that was removed
105        """
106        # Remove last element from sorted list to get max value
107        node = self.sorted_nodes.pop()
108        # Use the remove_node static method to detach the node from the stack
109        DoubleLinkedList.remove_node(node)
110        return node.val
111
112# The following code is how the MaxStack class would be used:
113# max_stack = MaxStack()
114# max_stack.push(x)
115# value = max_stack.pop()
116# value = max_stack.top()
117# max_val = max_stack.peekMax()
118# max_val = max_stack.popMax()
119

1class Node {
2    public int val;
3    public Node prev, next;
4
5    // Default constructor for Node
6    public Node() {
7    }
8
9    // Constructor with value for Node
10    public Node(int val) {
11        this.val = val;
12    }
13}
14
15class DoubleLinkedList {
16    private final Node head = new Node(); // Dummy head
17    private final Node tail = new Node(); // Dummy tail
18
19    // Constructor to initialize the doubly linked list
20    public DoubleLinkedList() {
21        head.next = tail;
22        tail.prev = head;
23    }
24
25    // Method to append a node with the given value to the end of the list
26    public Node append(int val) {
27        Node newNode = new Node(val);
28        newNode.next = tail;
29        newNode.prev = tail.prev;
30        tail.prev.next = newNode;
31        tail.prev = newNode;
32        return newNode;
33    }
34
35    // Static method to remove a given node from the list
36    public static Node remove(Node node) {
37        node.prev.next = node.next;
38        node.next.prev = node.prev;
39        return node;
40    }
41
42    // Method to pop the last node from the list
43    public Node pop() {
44        return remove(tail.prev);
45    }
46
47    // Method to peek at the last element's value without removing it
48    public int peek() {
49        return tail.prev.val;
50    }
51}
52
53class MaxStack {
54    private DoubleLinkedList stack = new DoubleLinkedList(); // Stack implemented as a doubly linked list
55    private TreeMap<Integer, List<Node>> map = new TreeMap<>(); // TreeMap to maintain max element and its occurrences
56
57    // Constructor for MaxStack
58    public MaxStack() {
59    }
60
61    // Method to push a value onto the stack
62    public void push(int x) {
63        Node node = stack.append(x); // Append new value to the stack
64        // Add the node reference to the TreeMap using its value as the key
65        map.computeIfAbsent(x, k -> new ArrayList<>()).add(node);
66    }
67
68    // Method to pop the top value off the stack
69    public int pop() {
70        Node node = stack.pop(); // Pop node from stack
71        List<Node> nodes = map.get(node.val);
72        // Remove the node reference from the list in TreeMap
73        // If the last occurrence, remove the entry from TreeMap
74        nodes.remove(nodes.size() - 1);
75        if (nodes.isEmpty()) {
76            map.remove(node.val);
77        }
78        return node.val;
79    }
80
81    // Method to retrieve the top value of the stack
82    public int top() {
83        return stack.peek();
84    }
85
86    // Method to get the maximum value from the stack
87    public int peekMax() {
88        return map.lastKey(); // The last key of TreeMap is the max value
89    }
90
91    // Method to remove and return the maximum value from the stack
92    public int popMax() {
93        int maxValue = peekMax(); // Get the current max value
94        List<Node> nodes = map.get(maxValue); // Get the list of nodes having the max value
95        Node node = nodes.remove(nodes.size() - 1); // Remove the last occurrence
96        if (nodes.isEmpty()) {
97            map.remove(maxValue); // Remove the entry from TreeMap if no more occurrences
98        }
99        DoubleLinkedList.remove(node); // Remove the node from the list
100        return maxValue;
101    }
102}
103
104/**
105 * Usage of the MaxStack class would look like the following:
106 * MaxStack maxStack = new MaxStack();
107 * maxStack.push(x);
108 * int param2 = maxStack.pop();
109 * int param3 = maxStack.top();
110 * int param4 = maxStack.peekMax();
111 * int param5 = maxStack.popMax();
112 */
113

1#include <list>
2#include <map>
3
4class MaxStack {
5public:
6    MaxStack() {
7        // Constructor of MaxStack. Initializes an empty stack.
8    }
9
10    void push(int x) {
11        // Pushes the value onto the stack.
12        stack.push_back(x);
13        // Inserts the value and its corresponding iterator from the list into the multimap.
14        valueToIterators.insert({x, --stack.end()});
15    }
16
17    int pop() {
18        // Pops the value from the top of the stack and returns it.
19        auto lastElemIter = --stack.end(); // Iterator to the last element in the list.
20        int value = *lastElemIter; // Value of the last element.
21
22        // Finds the iterator within the multimap associated with the value being popped.
23        auto valueIter = --valueToIterators.upper_bound(value);
24      
25        // Erase the element from both the list and the multimap.
26        valueToIterators.erase(valueIter);
27        stack.erase(lastElemIter);
28
29        // Returns the popped value.
30        return value;
31    }
32
33    int top() {
34        // Returns the top element of the stack without removing it.
35        return stack.back();
36    }
37
38    int peekMax() {
39        // Returns the maximum value in the stack without removing it.
40        return valueToIterators.rbegin()->first; // The first element of the reversed multimap is the max element.
41    }
42
43    int popMax() {
44        // Pops the maximum value from the stack and returns it.
45        auto maxValIter = --valueToIterators.end(); // Iterator to the element with max value in multimap.
46        auto stackIter = maxValIter->second; // Iterator in the list corresponding to the max value.
47        int maxValue = *stackIter; // Value of the max element.
48
49        // Erase the max element from both the list and the multimap.
50        valueToIterators.erase(maxValIter);
51        stack.erase(stackIter);
52
53        // Returns the popped maximum value.
54        return maxValue;
55    }
56
57private:
58    std::multimap<int, std::list<int>::iterator> valueToIterators; // Multimap storing values as keys and iterators as values.
59    std::list<int> stack; // The stack implementation using a linked list for constant-time insertion and deletion.
60};
61
62/**
63 * Your MaxStack object will be instantiated and called as such:
64 * MaxStack* obj = new MaxStack();
65 * obj->push(x);
66 * int param_2 = obj->pop();
67 * int param_3 = obj->top();
68 * int param_4 = obj->peekMax();
69 * int param_5 = obj->popMax();
70 */
71

1// This list represents the stack, using an array for simplicity in TypeScript.
2let stack: number[] = [];
3
4// This is a Map that will store the number as key and array of index positions as values to handle duplicates.
5let valueToIndices: Map<number, number[]> = new Map();
6
7// Pushes the value onto the stack.
8function push(x: number): void {
9  stack.push(x);
10  if (!valueToIndices.has(x)) {
11    valueToIndices.set(x, []);
12  }
13  valueToIndices.get(x)!.push(stack.length - 1);
14}
15
16// Pops the value from the top of the stack and returns it.
17function pop(): number {
18  const value = stack.pop()!;
19  const indices = valueToIndices.get(value)!;
20  indices.pop();
21  if (indices.length === 0) {
22    valueToIndices.delete(value);
23  }
24  return value;
25}
26
27// Returns the top element of the stack without removing it.
28function top(): number {
29  return stack[stack.length - 1];
30}
31
32// Returns the maximum value in the stack without removing it.
33function peekMax(): number {
34  return Math.max(...valueToIndices.keys());
35}
36
37// Pops the maximum value from the stack and returns it.
38function popMax(): number {
39  const maxValue = peekMax();
40  const indices = valueToIndices.get(maxValue)!;
41  const maxIndex = indices.pop()!;
42  stack.splice(maxIndex, 1);
43
44  if (indices.length === 0) {
45    valueToIndices.delete(maxValue);
46  } else {
47    // Update the indices in the map after removal of the max element.
48    valueToIndices.forEach((indices, value) => {
49      for (let i = 0; i < indices.length; i++) {
50        if (indices[i] > maxIndex) {
51          indices[i]--;
52        }
53      }
54    });
55  }
56
57  return maxValue;
58}
59

Time and Space Complexity

Time Complexity

push(x: int) -> None: Each push operation involves two steps: appending the value to the end of the double-linked list and adding a new node to the sorted list. Appending to the double-linked list is O(1) because it only involves changing a fixed number of pointers. Adding to the SortedList is O(log N) because it maintains the elements in sorted order. Overall, the time complexity for push is O(log N).
pop() -> int: The pop operation removes an element from the end of the double-linked list and also from the SortedList. Both of these operations take O(1) (removal from double-linked list) and O(log N) (removal from the sorted list because it may need to rebalance the data structure). Overall, the time complexity for pop is O(log N).
top() -> int: The top operation retrieves the last element of the double-linked list without removing it, which is a O(1) operation since it directly accesses the tail's previous node.
peekMax() -> int: The peekMax operation retrieves the last element of the SortedList, which is O(1) because it does not alter the sorted order and accesses the end of the list directly.
popMax() -> int: The popMax operation retrieves and removes the maximum element from the SortedList, which is O(log N) for removing from the sorted list. It also removes the corresponding node from the double-linked list, which is O(1). Overall, the time complexity for popMax is O(log N).

Space Complexity

The space complexity of the MaxStack class is primarily driven by the storage requirements of the double-linked list and the SortedList.
Each element in the stack is stored once in the double-linked list and once in the SortedList. Therefore, if the stack has N elements, the space complexity is O(N) as it needs to store each element twice.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which of the following is a good use case for backtracking?

Combinatorial problems

Random number generation

Topological sorting

Matrix multiplication

I don’t know