716. Max Stack
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)
topoperation 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 forpeekMaxandpopMax). -
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
sortedcontainersmodule 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 EvaluatorExample 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
5and append it to the doubly linked list. - Insert the node with value
5into the sorted list, which is now[5].
push(1)
- Create a new node with the value
1and append it to the doubly linked list. - Insert the node with value
1into the sorted list, which is now[1, 5].
push(10)
- Create a new node with the value
10and append it to the doubly linked list. - Insert the node with value
10into 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()
1191class 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 */
1131#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 */
711// 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}
59Time 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 isO(1)because it only involves changing a fixed number of pointers. Adding to theSortedListisO(log N)because it maintains the elements in sorted order. Overall, the time complexity for push isO(log N). -
pop() -> int: The pop operation removes an element from the end of the double-linked list and also from theSortedList. Both of these operations takeO(1)(removal from double-linked list) andO(log N)(removal from the sorted list because it may need to rebalance the data structure). Overall, the time complexity for pop isO(log N). -
top() -> int: The top operation retrieves the last element of the double-linked list without removing it, which is aO(1)operation since it directly accesses the tail's previous node. -
peekMax() -> int: The peekMax operation retrieves the last element of theSortedList, which isO(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 theSortedList, which isO(log N)for removing from the sorted list. It also removes the corresponding node from the double-linked list, which isO(1). Overall, the time complexity for popMax isO(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 hasNelements, the space complexity isO(N)as it needs to store each element twice.
Learn more about how to find time and space complexity quickly using problem constraints.
What does the following code do?
1def f(arr1, arr2):
2 i, j = 0, 0
3 new_arr = []
4 while i < len(arr1) and j < len(arr2):
5 if arr1[i] < arr2[j]:
6 new_arr.append(arr1[i])
7 i += 1
8 else:
9 new_arr.append(arr2[j])
10 j += 1
11 new_arr.extend(arr1[i:])
12 new_arr.extend(arr2[j:])
13 return new_arr
141public static List<Integer> f(int[] arr1, int[] arr2) {
2 int i = 0, j = 0;
3 List<Integer> newArr = new ArrayList<>();
4
5 while (i < arr1.length && j < arr2.length) {
6 if (arr1[i] < arr2[j]) {
7 newArr.add(arr1[i]);
8 i++;
9 } else {
10 newArr.add(arr2[j]);
11 j++;
12 }
13 }
14
15 while (i < arr1.length) {
16 newArr.add(arr1[i]);
17 i++;
18 }
19
20 while (j < arr2.length) {
21 newArr.add(arr2[j]);
22 j++;
23 }
24
25 return newArr;
26}
271function f(arr1, arr2) {
2 let i = 0, j = 0;
3 let newArr = [];
4
5 while (i < arr1.length && j < arr2.length) {
6 if (arr1[i] < arr2[j]) {
7 newArr.push(arr1[i]);
8 i++;
9 } else {
10 newArr.push(arr2[j]);
11 j++;
12 }
13 }
14
15 while (i < arr1.length) {
16 newArr.push(arr1[i]);
17 i++;
18 }
19
20 while (j < arr2.length) {
21 newArr.push(arr2[j]);
22 j++;
23 }
24
25 return newArr;
26}
27Recommended Readings
Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you
Linked List Cycle Given a linked list with potentially a loop determine whether the linked list from the first node contains a cycle in it For bonus points do this with constant space Parameters nodes The first node of a linked list with potentially a loop Result Whether there is a loop contained
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Want a Structured Path to Master System Design Too? Don’t Miss This!