Is Dinner Plate Stacks easy or hard?

Dinner Plate Stacks is classified as a Hard problem on LeetCode. The challenge comes from designing a data structure that efficiently supports push, pop, and popAtStack while always respecting leftmost and rightmost constraints.

How to solve Dinner Plate Stacks efficiently?

Store stacks in an indexed list and maintain two heaps: one for available stacks and one for non‑empty stacks. When pushing, always choose the smallest index from the available heap. When popping, remove from the largest index in the non‑empty heap. This ensures correct leftmost and rightmost behavior with O(log n) complexity.

What is the best approach for Dinner Plate Stacks?

The most efficient and widely accepted approach uses two priority queues (heaps). A min‑heap tracks the leftmost stack with available capacity, while a max‑heap tracks the rightmost non‑empty stack. This allows push and pop operations to run in O(log n) time while maintaining correct stack ordering.

What data structure is used in Dinner Plate Stacks?

The solution primarily combines stacks with priority queues (heaps). Stacks store the plate groups while heaps track which stacks are available for pushing or popping. Some implementations also use arrays or lists to index stacks efficiently.

What is the time complexity of Dinner Plate Stacks?

The optimized heap-based design performs push, pop, and popAtStack in O(log n) time due to heap operations. Brute force implementations may take O(n) time because they scan stacks to find available or non‑empty positions. Space complexity is O(n) for storing all stacks and elements.

Is Dinner Plate Stacks asked at Google, Amazon, or Meta?

Dinner Plate Stacks is a classic design problem involving stacks and priority queues. Variants of similar data structure design questions have appeared in interviews at companies like Google, Amazon, and Meta because they test system design thinking and efficient state management.

Is there a Python or Java solution for Dinner Plate Stacks?

Yes. Python implementations often use lists for stacks and the heapq module to manage priority queues. Java solutions typically use ArrayList for stacks and PriorityQueue for heap management, achieving the same O(log n) performance.

Description Hints 2 Solution Video 21:40

1172. Dinner Plate Stacks

Hard34.2% acceptance2 companies

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 * 10⁴
1 <= val <= 2 * 10⁴
0 <= index <= 10⁵
At most 2 * 10⁵ calls will be made to push, pop, and popAtStack.

Asked at 2 companies

Google Amazon

Topics

Hints open one at a time

Hint 1

Use a data structure to save the plate status. You may need to operate the exact index. Maintain the leftmost vacant stack and the rightmost non-empty stack.

Hint 2

Use a list of stack to store the plate status. Use heap to maintain the leftmost and rightmost valid stack.

21:40

Still stuck?Read 5 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class DinnerPlates:

  def __init__(self, capacity: int):
      

  def push(self, val: int) -> None:
      

  def pop(self) -> int:
      

  def popAtStack(self, index: int) -> int:
      


16# Your DinnerPlates object will be instantiated and called as such:
17# obj = DinnerPlates(capacity)
18# obj.push(val)
19# param_2 = obj.pop()
20# param_3 = obj.popAtStack(index)

Starter codePython 3Spaces: 4

Examples

Case 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],[],[],[],[],[]]

Your code is saved on this device.Solution