# Dinner Plate Stacks **Difficulty:** HARD [External](https://leetcode.com/problems/dinner-plate-stacks) Canonical: https://scaleengineer.com/dsa/problems/dinner-plate-stacks **Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design) **Data structures:** Hash Table, Stack, Heap (Priority Queue) --- ## Problem You have an infinite number of stacks arranged in a row and numbered (left to right) from `0`, each of the stacks has the same maximum capacity. Implement the `DinnerPlates` class: * `DinnerPlates(int capacity)` Initializes the object with the maximum capacity of the stacks `capacity`. * `void push(int val)` Pushes the given integer `val` into the leftmost stack with a size less than `capacity`. * `int pop()` Returns the value at the top of the rightmost non-empty stack and removes it from that stack, and returns `-1` if all the stacks are empty. * `int popAtStack(int index)` Returns the value at the top of the stack with the given index `index` and removes it from that stack or returns `-1` if the stack with that given index is empty. **Example 1:** **Input** ["DinnerPlates", "push", "push", "push", "push", "push", "popAtStack", "push", "push", "popAtStack", "popAtStack", "pop", "pop", "pop", "pop", "pop"] [[2], [1], [2], [3], [4], [5], [0], [20], [21], [0], [2], [], [], [], [], []] **Output** [null, null, null, null, null, null, 2, null, null, 20, 21, 5, 4, 3, 1, -1] **Explanation:** DinnerPlates D = DinnerPlates(2); // Initialize with capacity = 2 D.push(1); D.push(2); D.push(3); D.push(4); D.push(5); // The stacks are now: 2 4 1 3 5 ﹈ ﹈ ﹈ D.popAtStack(0); // Returns 2. The stacks are now: 4 1 3 5 ﹈ ﹈ ﹈ D.push(20); // The stacks are now: 20 4 1 3 5 ﹈ ﹈ ﹈ D.push(21); // The stacks are now: 20 4 21 1 3 5 ﹈ ﹈ ﹈ D.popAtStack(0); // Returns 20. The stacks are now: 4 21 1 3 5 ﹈ ﹈ ﹈ D.popAtStack(2); // Returns 21. The stacks are now: 4 1 3 5 ﹈ ﹈ ﹈ D.pop() // Returns 5. The stacks are now: 4 1 3 ﹈ ﹈ D.pop() // Returns 4. The stacks are now: 1 3 ﹈ ﹈ D.pop() // Returns 3. The stacks are now: 1 ﹈ D.pop() // Returns 1. There are no stacks. D.pop() // Returns -1. There are still no stacks. **Constraints:** * `1 <= capacity <= 2 * 104` * `1 <= val <= 2 * 104` * `0 <= index <= 105` * At most `2 * 105` calls will be made to `push`, `pop`, and `popAtStack`. # Approaches ## Brute Force using a List of Stacks This approach directly simulates the process described in the problem using a standard `ArrayList` to hold the stacks. For `push`, it searches for the first available spot from the left. For `pop`, it searches for the last non-empty stack from the right. While simple to conceive, its performance suffers from the linear scans required in these operations. **Time:** * `push(val)`: O(N), where N is the number of stacks. In the worst case, we scan all stacks. * `pop()`: O(N), where N is the number of stacks. In the worst case, we scan all stacks. * `popAtStack(index)`: O(N) in the worst case due to the linear-time trimming of trailing empty stacks. Accessing the stack is O(1). · **Space:** O(P), where P is the total number of plates (elements) pushed into the stacks across all operations. This is because we store every plate. **Pros:** Easy to understand and implement.; Uses standard Java collections. **Cons:** The `push` operation requires a linear scan from the left, which is O(N) where N is the number of stacks. This is inefficient if the first few stacks are always full.; The `pop` operation requires a linear scan from the right, which is O(N). This is inefficient if the rightmost stacks are often empty.; Will likely result in a 'Time Limit Exceeded' error for large inputs due to the O(N) complexity of push and pop operations. ### Explanation ### Data Structures We use an `ArrayList` of `Stack` objects to maintain the collection of dinner plate stacks. Each stack's maximum size is dictated by the `capacity`. ### Algorithm Details * **`push(val)`**: To push a value, we need to find the *leftmost* stack that is not full. The simplest way is to iterate through our list of stacks from index 0. The first stack we encounter with `size < capacity` is our target. We push the value onto it. If we iterate through all existing stacks and find them all full, we create a new stack, push the value, and add it to our list of stacks. * **`pop()`**: To pop from the *rightmost* non-empty stack, we iterate backward from the end of our list. The first non-empty stack we find is the one we pop from. After popping, we should clean up by removing any empty stacks that are now at the very end of the list. This prevents the list from containing a long tail of empty stacks, which would slow down subsequent `pop` calls. * **`popAtStack(index)`**: This is a direct operation. We access the stack at the given index, pop a value if it's not empty, and return it. We also perform the same cleanup of trailing empty stacks. ### Code Snippet ```java class DinnerPlates { private List> stacks; private int capacity; public DinnerPlates(int capacity) { this.capacity = capacity; this.stacks = new ArrayList<>(); } public void push(int val) { for (Stack stack : stacks) { if (stack.size() < capacity) { stack.push(val); return; } } Stack newStack = new Stack<>(); newStack.push(val); stacks.add(newStack); } public int pop() { // Start from the rightmost stack and find a non-empty one. for (int i = stacks.size() - 1; i >= 0; i--) { if (!stacks.get(i).isEmpty()) { int val = stacks.get(i).pop(); // Clean up trailing empty stacks while (!stacks.isEmpty() && stacks.get(stacks.size() - 1).isEmpty()) { stacks.remove(stacks.size() - 1); } return val; } } return -1; } public int popAtStack(int index) { if (index < 0 || index >= stacks.size() || stacks.get(index).isEmpty()) { return -1; } int val = stacks.get(index).pop(); // Clean up trailing empty stacks while (!stacks.isEmpty() && stacks.get(stacks.size() - 1).isEmpty()) { stacks.remove(stacks.size() - 1); } return val; } } ``` ### Algorithm * **Data Structures:** * Use an `ArrayList>` to store the stacks. * Store the `capacity` in an integer variable. * **Constructor `DinnerPlates(capacity)`:** * Initialize the `capacity` and the `ArrayList` of stacks. * **`push(val)` Operation:** 1. Iterate through the `stacks` list from the beginning (index 0). 2. For each stack, check if its size is less than `capacity`. 3. If such a stack is found, push `val` onto it and terminate the operation. 4. If the loop completes without finding any available stack, it means all existing stacks are full. 5. Create a new `Stack`, push `val` onto it, and add this new stack to the end of the `stacks` list. * **`pop()` Operation:** 1. Iterate through the `stacks` list from the end (`stacks.size() - 1`) backwards to 0. 2. For each stack, check if it is not empty. 3. If a non-empty stack is found, pop an element from it. 4. To prevent the list from growing with empty stacks at the end, trim any trailing empty stacks after a pop. 5. Return the popped value. 6. If the loop completes, it means all stacks are empty, so return -1. * **`popAtStack(index)` Operation:** 1. Validate the given `index`. If it's out of bounds or the stack at that index is empty, return -1. 2. Otherwise, pop an element from `stacks.get(index)`. 3. Perform the same trimming of trailing empty stacks as in `pop()`. 4. Return the popped value. ## Optimized Approach using TreeMap and TreeSet To overcome the performance issues of the naive approach, we can use more suitable data structures. A `TreeMap` can store the stacks, and a `TreeSet` can track which stacks have available capacity. This allows us to find the target stacks for `push` and `pop` operations in logarithmic time instead of linear time. **Time:** * `push(val)`: O(log N), where N is the number of stacks. * `pop()`: O(log N). * `popAtStack(index)`: O(log N). All operations are efficient due to the logarithmic time complexity of `TreeMap` and `TreeSet` operations. · **Space:** O(P), where P is the total number of plates pushed. The `TreeMap` and `TreeSet` store metadata, but the dominant factor is the storage of the plates themselves. **Pros:** Highly efficient, with all operations running in logarithmic time.; Scales well for a large number of operations and stacks, passing all constraints.; Gracefully handles sparse stacks (gaps created by `popAtStack`). **Cons:** More complex implementation due to managing multiple coordinated data structures.; Slightly higher memory overhead due to the `TreeMap` and `TreeSet` structures compared to a simple list. ### Explanation ### Data Structures This optimized solution uses two primary data structures to manage the stacks efficiently: 1. **`TreeMap> stacks`**: This maps a stack's index to the stack itself (an `ArrayDeque` is used as the stack implementation). A `TreeMap` is chosen because it keeps its keys (the stack indices) in sorted order. This property is crucial for the `pop()` operation, as we can find the rightmost non-empty stack in O(log N) time by calling `stacks.lastKey()`. 2. **`TreeSet availableStacks`**: This stores the indices of all stacks that currently have a size less than `capacity`. A `TreeSet` maintains these indices in sorted order, which is perfect for the `push(val)` operation. We can find the *leftmost* stack with available space in O(log K) time by calling `availableStacks.first()`, where K is the number of non-full stacks. ### Algorithm Details * **`push(val)`**: Instead of scanning, we directly query `availableStacks`. If it's not empty, `first()` gives us the index of the leftmost stack with space. We push to it. If it becomes full, we remove its index from `availableStacks`. If `availableStacks` is empty, we know we need a new stack at the end of the current row, so we create one at index `stacks.lastKey() + 1`. * **`pop()`**: We find the rightmost non-empty stack by getting the largest key in our `stacks` `TreeMap` (`lastKey()`). Then, we simply call `popAtStack` on that index. This avoids a linear scan. * **`popAtStack(index)`**: We pop from the specified stack. The key is to correctly update our data structures. If a pop makes a stack empty, we remove it from the `stacks` map. If a pop makes a *full* stack become *not full*, we add its index to `availableStacks` so it can be used for future pushes. ### Code Snippet ```java import java.util.*; class DinnerPlates { private int capacity; private TreeMap> stacks; private TreeSet availableStacks; public DinnerPlates(int capacity) { this.capacity = capacity; this.stacks = new TreeMap<>(); this.availableStacks = new TreeSet<>(); } public void push(int val) { if (availableStacks.isEmpty()) { int newIndex = stacks.isEmpty() ? 0 : stacks.lastKey() + 1; availableStacks.add(newIndex); } int indexToPush = availableStacks.first(); stacks.computeIfAbsent(indexToPush, k -> new ArrayDeque<>()).push(val); if (stacks.get(indexToPush).size() == capacity) { availableStacks.remove(indexToPush); } } public int pop() { if (stacks.isEmpty()) { return -1; } int indexToPop = stacks.lastKey(); return popAtStack(indexToPop); } public int popAtStack(int index) { if (!stacks.containsKey(index) || stacks.get(index).isEmpty()) { return -1; } Deque stack = stacks.get(index); boolean wasFull = (stack.size() == capacity); int val = stack.pop(); if (wasFull) { availableStacks.add(index); } if (stack.isEmpty()) { stacks.remove(index); availableStacks.remove(index); } return val; } } ``` ### Algorithm * **Data Structures:** * `TreeMap> stacks`: A map from a stack's index to the stack itself (using a `Deque`). `TreeMap` keeps indices sorted, allowing efficient retrieval of the rightmost stack. * `TreeSet availableStacks`: A sorted set of indices of stacks that are not full. This allows efficient retrieval of the leftmost available stack. * `int capacity`: The maximum capacity of each stack. * **Constructor `DinnerPlates(capacity)`:** * Initialize `capacity`, the `TreeMap`, and the `TreeSet`. * **`push(val)` Operation:** 1. Check if `availableStacks` is empty. If so, it means all existing stacks are full. Determine the index for a new stack (which will be `stacks.lastKey() + 1`, or 0 if no stacks exist) and add this index to `availableStacks`. 2. Get the smallest index from `availableStacks` using `first()`. This is the leftmost stack with available space. 3. Get the stack at this index from the `stacks` map (creating it if it doesn't exist) and push `val` onto it. 4. If the stack's size now equals `capacity`, remove its index from `availableStacks`. * **`pop()` Operation:** 1. Check if the `stacks` map is empty. If so, return -1. 2. Find the index of the rightmost non-empty stack using `stacks.lastKey()`. 3. Delegate the actual pop logic to `popAtStack(index)` to ensure consistency. * **`popAtStack(index)` Operation:** 1. Check if a stack exists at the given `index` and if it's not empty. If not, return -1. 2. Note whether the stack was full before the pop operation. 3. Pop the value from the stack. 4. If the stack becomes empty, remove it entirely from the `stacks` map and also from `availableStacks`. 5. If the stack was full before popping, it now has space, so add its index back to `availableStacks`. 6. Return the popped value. # Solutions ### Java ```java class DinnerPlates { private int capacity ; private List < Deque < Integer >> stacks = new ArrayList <>(); private TreeSet < Integer > notFull = new TreeSet <>(); public DinnerPlates ( int capacity ) { this . capacity = capacity ; } public void push ( int val ) { if ( notFull . isEmpty ()) { stacks . add ( new ArrayDeque <>()); stacks . get ( stacks . size () - 1 ). push ( val ); if ( capacity > 1 ) { notFull . add ( stacks . size () - 1 ); } } else { int index = notFull . first (); stacks . get ( index ). push ( val ); if ( stacks . get ( index ). size () == capacity ) { notFull . pollFirst (); } } } public int pop () { return popAtStack ( stacks . size () - 1 ); } public int popAtStack ( int index ) { if ( index < 0 || index >= stacks . size () || stacks . get ( index ). isEmpty ()) { return - 1 ; } int val = stacks . get ( index ). pop (); if ( index == stacks . size () - 1 && stacks . get ( stacks . size () - 1 ). isEmpty ()) { while (! stacks . isEmpty () && stacks . get ( stacks . size () - 1 ). isEmpty ()) { notFull . remove ( stacks . size () - 1 ); stacks . remove ( stacks . size () - 1 ); } } else { notFull . add ( index ); } return val ; } } /** * Your DinnerPlates object will be instantiated and called as such: * DinnerPlates obj = new DinnerPlates(capacity); * obj.push(val); * int param_2 = obj.pop(); * int param_3 = obj.popAtStack(index); */ ``` ### CPP ```cpp class DinnerPlates { public: DinnerPlates ( int capacity ) { this -> capacity = capacity ; } void push ( int val ) { if ( notFull . empty ()) { stacks . emplace_back ( stack < int > ()); stacks . back (). push ( val ); if ( capacity > 1 ) { notFull . insert ( stacks . size () - 1 ); } } else { int index = * notFull . begin (); stacks [ index ]. push ( val ); if ( stacks [ index ]. size () == capacity ) { notFull . erase ( index ); } } } int pop () { return popAtStack ( stacks . size () - 1 ); } int popAtStack ( int index ) { if ( index < 0 || index >= stacks . size () || stacks [ index ]. empty ()) { return - 1 ; } int val = stacks [ index ]. top (); stacks [ index ]. pop (); if ( index == stacks . size () - 1 && stacks [ index ]. empty ()) { while ( ! stacks . empty () && stacks . back (). empty ()) { notFull . erase ( stacks . size () - 1 ); stacks . pop_back (); } } else { notFull . insert ( index ); } return val ; } private: int capacity ; vector < stack < int >> stacks ; set < int > notFull ; }; /** * Your DinnerPlates object will be instantiated and called as such: * DinnerPlates* obj = new DinnerPlates(capacity); * obj->push(val); * int param_2 = obj->pop(); * int param_3 = obj->popAtStack(index); */ ``` ### Python ```python from sortedcontainers import SortedSet class DinnerPlates : def __init__ ( self , capacity : int ): self . capacity = capacity self . stacks = [] self . not_full = SortedSet () def push ( self , val : int ) -> None : if not self . not_full : self . stacks . append ([ val ]) if self . capacity > 1 : self . not_full . add ( len ( self . stacks ) - 1 ) else : index = self . not_full [ 0 ] self . stacks [ index ]. append ( val ) if len ( self . stacks [ index ]) == self . capacity : self . not_full . discard ( index ) def pop ( self ) -> int : return self . popAtStack ( len ( self . stacks ) - 1 ) def popAtStack ( self , index : int ) -> int : if index < 0 or index >= len ( self . stacks ) or not self . stacks [ index ]: return - 1 val = self . stacks [ index ]. pop () if index == len ( self . stacks ) - 1 and not self . stacks [ - 1 ]: while self . stacks and not self . stacks [ - 1 ]: self . not_full . discard ( len ( self . stacks ) - 1 ) self . stacks . pop () else : self . not_full . add ( index ) return val # Your DinnerPlates object will be instantiated and called as such: # obj = DinnerPlates(capacity) # obj.push(val) # param_2 = obj.pop() # param_3 = obj.popAtStack(index) ```