Dinner Plate Stacks - Solution & Explanation

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

HardHash Table Stack Design Heap (Priority Queue)29 min readAsked at: Amazon, Google

Practice this problem

Problem Statement

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.

Approach Overview

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.

Approach 1: Using List with Direct Indexing

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.

Code

Python

Complexity

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.

Try this approach in the editor →

Approach 2: Using Two Priority Queues

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.

Code

Java

Complexity

Time Complexity: O(log n) due to the priority queue operations for maintain indices.
Space Complexity: O(n) for storing elements in the stacks.

Try this approach in the editor →

Approach 3: Brute Force Approach

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.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n^2)
Space Complexity: O(1)

Try this approach in the editor →

Approach 4: Optimized Approach Using Mathematical Properties

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.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n log n)
Space Complexity: O(1)

Try this approach in the editor →

Approach 5: Stack Array + Ordered Set

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:

We first check if 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.
If 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:

We first check if 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.
If 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.
Finally, return val.

For the pop() operation:

We directly call 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.

Code

Python Java C++Go TypeScript

Python

Java

C++

TypeScript

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Using List with Direct Indexing	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.
Using Two Priority Queues	Time Complexity: O(log n) due to the priority queue operations for maintain indices. Space Complexity: O(n) for storing elements in the stacks.
Brute Force Approach	Time Complexity: O(n^2) Space Complexity: O(1)
Optimized Approach Using Mathematical Properties	Time Complexity: O(n log n) Space Complexity: O(1)
Stack Array + Ordered Set	—

Detailed Complexity Analysis

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

Video Solution

1172. Dinner Plate Stacks (Leetcode Hard) • Programming Live with Larry • 2,368 views views

Watch 5 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Dinner Plate Stacks with our built-in code editor and test cases.

Practice on FleetCode

Two Sum

Longest Substring Without Repeating Characters

Problem Info

DifficultyHard

Acceptance33.6%

Approaches5

Reading time29 min

Asked at

Amazon Google

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Using List with Direct Indexing

Code

Complexity

Approach 2: Using Two Priority Queues

Code

Complexity

Approach 3: Brute Force Approach

Code

Complexity

Approach 4: Optimized Approach Using Mathematical Properties

Code

Complexity

Approach 5: Stack Array + Ordered Set

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents