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 * 1041 <= val <= 2 * 1040 <= index <= 1052 * 105 calls will be made to push, pop, and popAtStack.Problem Overview: You need to design a data structure that simulates stacks of dinner plates. Each stack has a fixed capacity. When pushing, the value must go into the leftmost stack that is not full. When popping, values are removed from the rightmost non‑empty stack. The structure must also support popAtStack(index) which pops from a specific stack.
Approach 1: Brute Force Approach (Push/Pop Scan) (Time: O(n), Space: O(n))
The simplest implementation stores stacks in an array or list. For push, iterate from the beginning until you find the first stack whose size is below the capacity. For pop, iterate from the end until you find a non‑empty stack. popAtStack directly accesses the requested index if it exists. This approach is easy to implement but inefficient because every push or pop may scan multiple stacks. The total space grows with the number of elements since every stack is stored explicitly.
Approach 2: Using List with Direct Indexing (Time: O(n) worst case, Space: O(n))
This design still stores stacks in a list but optimizes stack access using direct indexing. Each stack is represented as a list and new stacks are appended when needed. push tries to place elements in earlier stacks when possible, while pop removes from the last stack and trims empty stacks from the end. Although worst‑case scanning still exists, direct indexing simplifies operations like popAtStack. The structure relies on basic stack behavior and sequential storage.
Approach 3: Using Two Priority Queues (Time: O(log n), Space: O(n))
This is the common interview solution. Maintain two heaps: a min‑heap storing indices of stacks that are not full, and a max‑heap storing indices of stacks that are not empty. When pushing, extract the smallest index from the available heap and insert the element into that stack. When popping, remove from the stack with the largest index using the max‑heap. Heaps automatically track the correct stack positions, ensuring operations stay logarithmic. This approach combines priority queues with indexed stacks and avoids expensive scans.
Approach 4: Optimized Approach Using Mathematical Properties (Time: O(1)–O(log n), Space: O(n))
Another optimization uses predictable stack positions derived from capacity and insertion order. Instead of scanning stacks, maintain structural properties about where the next available slot should be. The logic tracks partially filled stacks and reuses them efficiently when popAtStack creates gaps. Mathematical indexing removes redundant checks and keeps push/pop close to constant time in many scenarios. This version still stores stacks explicitly but minimizes bookkeeping overhead compared with heap-heavy designs.
Recommended for interviews: The two‑priority‑queue solution is usually what interviewers expect. It clearly demonstrates how to manage dynamic resources with heaps and indexed stacks. Showing the brute force version first proves you understand the constraints, but implementing the heap-based design highlights stronger skills with data structure coordination and efficient state tracking.
This approach utilizes a list of stacks (each stack is a list) to store the elements and maintain the stacks' behavior. Two primary indices are maintained: one to track the leftmost available spot (i.e., where push is possible) and another to track the rightmost non-empty stack (i.e., the possible candidates for pop operations). The push and pop operations adjust these indices accordingly to manage stacks efficiently.
In the Python implementation, a list of stacks is used where each entry is a stack (list). The variables leftmost and rightmost track the indices, allowing efficient push and pop operations by keeping track of the available stacks.
Python
Time Complexity: O(1) average for push and pop since we maintain indices, avoiding unnecessary scans.
Space Complexity: O(n) where n is the number of values pushed because we are adding values to lists.
This approach utilizes two priority queues to manage the indices of stacks: one for the leftmost non-full stack (for pushing) and another for the rightmost non-empty stack (for popping). The priority queues allow efficient insertion and retrieval operations, making the overall approach efficient.
In the Java implementation, `TreeSet` is used to manage available indices efficiently. The `push` operation finds and pushes to the leftmost available stack while the `pop` operation attempts to access the rightmost non-empty stack. TreeSet provides ordered and efficient access to indices.
Java
Time Complexity: O(log n) due to the priority queue operations for maintain indices.
Space Complexity: O(n) for storing elements in the stacks.
This approach involves checking all possible combinations or permutations to find the solution. It's simple and ensures correctness but may not be efficient for large inputs.
This C code gives a blueprint for implementing the brute force solution. You'll need to fill in the logic according to the specific problem details.
Time Complexity: O(n^2)
Space Complexity: O(1)
This approach leverages mathematical properties or data structures to achieve better efficiency. It reduces redundant computations and works well for larger inputs.
This C code provides a skeleton for implementing an optimized solution using mathematical properties. Implement the exact logic for your specific problem.
Time Complexity: O(n log n)
Space Complexity: O(1)
We define the following data structures or variables:
capacity: The capacity of each stack;stacks: Stack array, used to store all stacks, each with a maximum capacity of capacity;not_full: Ordered set, used to store the indices of all non-full stacks in the stack array.For the push(val) operation:
not_full is empty. If it is, it means there are no non-full stacks, so we need to create a new stack and push val into it. At this point, we check if the capacity capacity is greater than 1. If it is, we add the index of this stack to not_full.not_full is not empty, it means there are non-full stacks. We take out the smallest index index from not_full, and push val into stacks[index]. At this point, if the capacity of stacks[index] equals capacity, we remove index from not_full.For the popAtStack(index) operation:
index is within the index range of stacks. If it is not, we directly return -1. If stacks[index] is empty, we also directly return -1.stacks[index] is not empty, we pop the top element val from stacks[index]. If index equals the length of stacks minus 1, it means stacks[index] is the last stack. If it is empty, we loop to remove the index of the last stack from not_full, and remove the last stack from the stack array stacks, until the last stack is not empty, or the stack array stacks is empty. Otherwise, if stacks[index] is not the last stack, we add index to not_full.val.For the pop() operation:
popAtStack(stacks.length - 1).The time complexity is (n times log n), and the space complexity is O(n). Here, n is the number of operations.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Using List with Direct Indexing | Time Complexity: O(1) average for push and pop since we maintain indices, avoiding unnecessary scans. |
| Using Two Priority Queues | Time Complexity: O(log n) due to the priority queue operations for maintain indices. |
| Brute Force Approach | Time Complexity: O(n^2) |
| Optimized Approach Using Mathematical Properties | Time Complexity: O(n log n) |
| Stack Array + Ordered Set | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Scan | O(n) per push/pop | O(n) | Good for understanding the problem or quick prototypes |
| List with Direct Indexing | O(n) worst case | O(n) | Simpler implementation with predictable stack indexing |
| Two Priority Queues | O(log n) | O(n) | Best general solution; efficient push and pop operations |
| Mathematical Optimization | O(1)–O(log n) | O(n) | When minimizing heap operations or leveraging predictable stack indices |
1172. Dinner Plate Stacks (Leetcode Hard) • Programming Live with Larry • 2,293 views views
Watch 6 more video solutions →Practice Dinner Plate Stacks with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor