Dinner Plate Stacks solution and explanation
Google
5 more videos on this problem
1172. Dinner Plate Stacks (Leetcode Hard)Programming Live with Larry · 21:40 · 2K views
花花酱 LeetCode 1172. Dinner Plate Stacks - 刷题找工作 EP266Hua Hua · 19:16 · 1K views
LeetCode 1172 Dinner Plate StackscoderZ · 9:17 · 789 views
Leetcode 1172. Dinner Plate StacksFearless Learner · 9:57 · 774 views
【每日一题】1172. Dinner Plate Stacks, 09/28/2019Huifeng Guan · 44:43 · 245 views
No Sound Leetcode 1172: Dinner Plate StacksExtremeProgrammer · 3:21 · 24 views
The 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 stackscapacity.void push(int val)Pushes the given integervalinto the leftmost stack with a size less thancapacity.int pop()Returns the value at the top of the rightmost non-empty stack and removes it from that stack, and returns-1if all the stacks are empty.int popAtStack(int index)Returns the value at the top of the stack with the given indexindexand removes it from that stack or returns-1if 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 <= 105- At most
2 * 105calls will be made topush,pop, andpopAtStack.
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.
class DinnerPlates:
def __init__(self, capacity: int):
self.capacity = capacity
self.stacks = []
self.leftmost = 0
self.rightmost = -1
def push(self, val: int) -> None:
while self.leftmost < len(self.stacks) and len(self.stacks[self.leftmost]) == self.capacity:
self.leftmost += 1
if self.leftmost == len(self.stacks):
self.stacks.append([])
self.stacks[self.leftmost].append(val)
self.rightmost = max(self.rightmost, self.leftmost)
def pop(self) -> int:
while self.rightmost >= 0 and not self.stacks[self.rightmost]:
self.rightmost -= 1
if self.rightmost == -1:
return -1
val = self.stacks[self.rightmost].pop()
if not self.stacks[self.rightmost]:
self.leftmost = min(self.leftmost, self.rightmost)
return val
def popAtStack(self, index: int) -> int:
if 0 <= index < len(self.stacks) and self.stacks[index]:
val = self.stacks[index].pop()
self.leftmost = min(self.leftmost, index)
return val
return -1In 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.
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.
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.
import java.util.*;
class DinnerPlates {
private final List<Stack<Integer>> stacks = new ArrayList<>();
private final TreeSet<Integer> available = new TreeSet<>();
private final int capacity;
public DinnerPlates(int capacity) {
this.capacity = capacity;
}
public void push(int val) {
if (available.isEmpty() || available.first() >= stacks.size()) {
stacks.add(new Stack<Integer>());
available.add(stacks.size() - 1);
}
int index = available.first();
stacks.get(index).push(val);
if (stacks.get(index).size() == capacity) {
available.pollFirst();
}
}
public int pop() {
for (int i = stacks.size() - 1; i >= 0; i--) {
if (!stacks.get(i).isEmpty()) {
int val = stacks.get(i).pop();
available.add(i);
return val;
}
}
return -1;
}
public int popAtStack(int index) {
if (index < stacks.size() && !stacks.get(index).isEmpty()) {
int val = stacks.get(index).pop();
available.add(index);
return val;
}
return -1;
}
}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.
Time Complexity: O(log n) due to the priority queue operations for maintain indices.
Space Complexity: O(n) for storing elements in the stacks.
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.
def solve():
# Add solution logic here
print('Brute Force solution in Python')
solve()public class Main {
public static void solve() {
// Add solution logic here
System.out.println("Brute Force solution in Java");
}
public static void main(String[] args) {
solve();
}
}#include <iostream>
void solve() {
// Add solution logic here
std::cout << "Brute Force solution in C++";
}
int main() {
solve();
return 0;
}function solve() {
// Add solution logic here
console.log('Brute Force solution in JavaScript');
}
solve();#include <stdio.h>
void solve() {
// Add solution logic here
printf("Brute Force solution in C");
}
int main() {
solve();
return 0;
}using System;
class Program {
static void Solve() {
// Add solution logic here
Console.WriteLine("Brute Force solution in C#");
}
static void Main(string[] args) {
Solve();
}
}This Python code provides a structure for the brute force solution. Insert the relevant logic as necessary.
Time Complexity: O(n^2)
Space Complexity: O(1)
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.
def solve():
# Optimized logic goes here
print('Optimized solution in Python')
solve()public class Main {
public static void solve() {
// Optimized logic goes here
System.out.println("Optimized solution in Java");
}
public static void main(String[] args) {
solve();
}
}#include <iostream>
void solve() {
// Optimized logic goes here
std::cout << "Optimized solution in C++";
}
int main() {
solve();
return 0;
}function solve() {
// Optimized logic goes here
console.log('Optimized solution in JavaScript');
}
solve();#include <stdio.h>
void solve() {
// Optimized logic goes here
printf("Optimized solution in C");
}
int main() {
solve();
return 0;
}using System;
class Program {
static void Solve() {
// Optimized logic goes here
Console.WriteLine("Optimized solution in C#");
}
static void Main(string[] args) {
Solve();
}
}This Python code serves as a framework for implementing a more optimized solution. Write your problem-specific logic here.
Time Complexity: O(n log n)
Space Complexity: O(1)
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 ofcapacity;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_fullis empty. If it is, it means there are no non-full stacks, so we need to create a new stack and pushvalinto it. At this point, we check if the capacitycapacityis greater than1. If it is, we add the index of this stack tonot_full. - If
not_fullis not empty, it means there are non-full stacks. We take out the smallest indexindexfromnot_full, and pushvalintostacks[index]. At this point, if the capacity ofstacks[index]equalscapacity, we removeindexfromnot_full.
For the popAtStack(index) operation:
- We first check if
indexis within the index range ofstacks. If it is not, we directly return-1. Ifstacks[index]is empty, we also directly return-1. - If
stacks[index]is not empty, we pop the top elementvalfromstacks[index]. Ifindexequals the length ofstacksminus1, it meansstacks[index]is the last stack. If it is empty, we loop to remove the index of the last stack fromnot_full, and remove the last stack from the stack arraystacks, until the last stack is not empty, or the stack arraystacksis empty. Otherwise, ifstacks[index]is not the last stack, we addindextonot_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.
class DinnerPlates {
capacity: number;
stacks: number[][];
notFull: TreeSet<number>;
constructor(capacity: number) {
this.capacity = capacity;
this.stacks = [];
this.notFull = new TreeSet<number>();
}
push(val: number): void {
if (this.notFull.size() === 0) {
this.stacks.push([val]);
if (this.capacity > 1) {
this.notFull.add(this.stacks.length - 1);
}
} else {
const index = this.notFull.first()!;
this.stacks[index].push(val);
if (this.stacks[index].length === this.capacity) {
this.notFull.delete(index);
}
}
}
pop(): number {
return this.popAtStack(this.stacks.length - 1);
}
popAtStack(index: number): number {
if (index < 0 || index >= this.stacks.length || this.stacks[index].length === 0) {
return -1;
}
const val = this.stacks[index].pop()!;
if (index === this.stacks.length - 1 && this.stacks[index].length === 0) {
while (this.stacks.length > 0 && this.stacks[this.stacks.length - 1].length === 0) {
this.notFull.delete(this.stacks.length - 1);
this.stacks.pop();
}
} else {
this.notFull.add(index);
}
return val;
}
}
type Compare<T> = (lhs: T, rhs: T) => number;
class RBTreeNode<T = number> {
data: T;
count: number;
left: RBTreeNode<T> | null;
right: RBTreeNode<T> | null;
parent: RBTreeNode<T> | null;
color: number;
constructor(data: T) {
this.data = data;
this.left = this.right = this.parent = null;
this.color = 0;
this.count = 1;
}
sibling(): RBTreeNode<T> | null {
if (!this.parent) return null; // sibling null if no parent
return this.isOnLeft() ? this.parent.right : this.parent.left;
}
isOnLeft(): boolean {
return this === this.parent!.left;
}
hasRedChild(): boolean {
return (
Boolean(this.left && this.left.color === 0) ||
Boolean(this.right && this.right.color === 0)
);
}
}
class RBTree<T> {
root: RBTreeNode<T> | null;
lt: (l: T, r: T) => boolean;
constructor(compare: Compare<T> = (l: T, r: T) => (l < r ? -1 : l > r ? 1 : 0)) {
this.root = null;
this.lt = (l: T, r: T) => compare(l, r) < 0;
}
rotateLeft(pt: RBTreeNode<T>): void {
const right = pt.right!;
pt.right = right.left;
if (pt.right) pt.right.parent = pt;
right.parent = pt.parent;
if (!pt.parent) this.root = right;
else if (pt === pt.parent.left) pt.parent.left = right;
else pt.parent.right = right;
right.left = pt;
pt.parent = right;
}
rotateRight(pt: RBTreeNode<T>): void {
const left = pt.left!;
pt.left = left.right;
if (pt.left) pt.left.parent = pt;
left.parent = pt.parent;
if (!pt.parent) this.root = left;
else if (pt === pt.parent.left) pt.parent.left = left;
else pt.parent.right = left;
left.right = pt;
pt.parent = left;
}
swapColor(p1: RBTreeNode<T>, p2: RBTreeNode<T>): void {
const tmp = p1.color;
p1.color = p2.color;
p2.color = tmp;
}
swapData(p1: RBTreeNode<T>, p2: RBTreeNode<T>): void {
const tmp = p1.data;
p1.data = p2.data;
p2.data = tmp;
}
fixAfterInsert(pt: RBTreeNode<T>): void {
let parent = null;
let grandParent = null;
while (pt !== this.root && pt.color !== 1 && pt.parent?.color === 0) {
parent = pt.parent;
grandParent = pt.parent.parent;
/* Case : A
Parent of pt is left child of Grand-parent of pt */
if (parent === grandParent?.left) {
const uncle = grandParent.right;
/* Case : 1
The uncle of pt is also red
Only Recoloring required */
if (uncle && uncle.color === 0) {
grandParent.color = 0;
parent.color = 1;
uncle.color = 1;
pt = grandParent;
} else {
/* Case : 2
pt is right child of its parent
Left-rotation required */
if (pt === parent.right) {
this.rotateLeft(parent);
pt = parent;
parent = pt.parent;
}
/* Case : 3
pt is left child of its parent
Right-rotation required */
this.rotateRight(grandParent);
this.swapColor(parent!, grandParent);
pt = parent!;
}
} else {
/* Case : B
Parent of pt is right child of Grand-parent of pt */
const uncle = grandParent!.left;
/* Case : 1
The uncle of pt is also red
Only Recoloring required */
if (uncle != null && uncle.color === 0) {
grandParent!.color = 0;
parent.color = 1;
uncle.color = 1;
pt = grandParent!;
} else {
/* Case : 2
pt is left child of its parent
Right-rotation required */
if (pt === parent.left) {
this.rotateRight(parent);
pt = parent;
parent = pt.parent;
}
/* Case : 3
pt is right child of its parent
Left-rotation required */
this.rotateLeft(grandParent!);
this.swapColor(parent!, grandParent!);
pt = parent!;
}
}
}
this.root!.color = 1;
}
delete(val: T): boolean {
const node = this.find(val);
if (!node) return false;
node.count--;
if (!node.count) this.deleteNode(node);
return true;
}
deleteAll(val: T): boolean {
const node = this.find(val);
if (!node) return false;
this.deleteNode(node);
return true;
}
deleteNode(v: RBTreeNode<T>): void {
const u = BSTreplace(v);
// True when u and v are both black
const uvBlack = (u === null || u.color === 1) && v.color === 1;
const parent = v.parent!;
if (!u) {
// u is null therefore v is leaf
if (v === this.root) this.root = null;
// v is root, making root null
else {
if (uvBlack) {
// u and v both black
// v is leaf, fix double black at v
this.fixDoubleBlack(v);
} else {
// u or v is red
if (v.sibling()) {
// sibling is not null, make it red"
v.sibling()!.color = 0;
}
}
// delete v from the tree
if (v.isOnLeft()) parent.left = null;
else parent.right = null;
}
return;
}
if (!v.left || !v.right) {
// v has 1 child
if (v === this.root) {
// v is root, assign the value of u to v, and delete u
v.data = u.data;
v.left = v.right = null;
} else {
// Detach v from tree and move u up
if (v.isOnLeft()) parent.left = u;
else parent.right = u;
u.parent = parent;
if (uvBlack) this.fixDoubleBlack(u);
// u and v both black, fix double black at u
else u.color = 1; // u or v red, color u black
}
return;
}
// v has 2 children, swap data with successor and recurse
this.swapData(u, v);
this.deleteNode(u);
// find node that replaces a deleted node in BST
function BSTreplace(x: RBTreeNode<T>): RBTreeNode<T> | null {
// when node have 2 children
if (x.left && x.right) return successor(x.right);
// when leaf
if (!x.left && !x.right) return null;
// when single child
return x.left ?? x.right;
}
// find node that do not have a left child
// in the subtree of the given node
function successor(x: RBTreeNode<T>): RBTreeNode<T> {
let temp = x;
while (temp.left) temp = temp.left;
return temp;
}
}
fixDoubleBlack(x: RBTreeNode<T>): void {
if (x === this.root) return; // Reached root
const sibling = x.sibling();
const parent = x.parent!;
if (!sibling) {
// No sibiling, double black pushed up
this.fixDoubleBlack(parent);
} else {
if (sibling.color === 0) {
// Sibling red
parent.color = 0;
sibling.color = 1;
if (sibling.isOnLeft()) this.rotateRight(parent);
// left case
else this.rotateLeft(parent); // right case
this.fixDoubleBlack(x);
} else {
// Sibling black
if (sibling.hasRedChild()) {
// at least 1 red children
if (sibling.left && sibling.left.color === 0) {
if (sibling.isOnLeft()) {
// left left
sibling.left.color = sibling.color;
sibling.color = parent.color;
this.rotateRight(parent);
} else {
// right left
sibling.left.color = parent.color;
this.rotateRight(sibling);
this.rotateLeft(parent);
}
} else {
if (sibling.isOnLeft()) {
// left right
sibling.right!.color = parent.color;
this.rotateLeft(sibling);
this.rotateRight(parent);
} else {
// right right
sibling.right!.color = sibling.color;
sibling.color = parent.color;
this.rotateLeft(parent);
}
}
parent.color = 1;
} else {
// 2 black children
sibling.color = 0;
if (parent.color === 1) this.fixDoubleBlack(parent);
else parent.color = 1;
}
}
}
}
insert(data: T): boolean {
// search for a position to insert
let parent = this.root;
while (parent) {
if (this.lt(data, parent.data)) {
if (!parent.left) break;
else parent = parent.left;
} else if (this.lt(parent.data, data)) {
if (!parent.right) break;
else parent = parent.right;
} else break;
}
// insert node into parent
const node = new RBTreeNode(data);
if (!parent) this.root = node;
else if (this.lt(node.data, parent.data)) parent.left = node;
else if (this.lt(parent.data, node.data)) parent.right = node;
else {
parent.count++;
return false;
}
node.parent = parent;
this.fixAfterInsert(node);
return true;
}
find(data: T): RBTreeNode<T> | null {
let p = this.root;
while (p) {
if (this.lt(data, p.data)) {
p = p.left;
} else if (this.lt(p.data, data)) {
p = p.right;
} else break;
}
return p ?? null;
}
*inOrder(root: RBTreeNode<T> = this.root!): Generator<T, undefined, void> {
if (!root) return;
for (const v of this.inOrder(root.left!)) yield v;
yield root.data;
for (const v of this.inOrder(root.right!)) yield v;
}
*reverseInOrder(root: RBTreeNode<T> = this.root!): Generator<T, undefined, void> {
if (!root) return;
for (const v of this.reverseInOrder(root.right!)) yield v;
yield root.data;
for (const v of this.reverseInOrder(root.left!)) yield v;
}
}
class TreeSet<T = number> {
_size: number;
tree: RBTree<T>;
compare: Compare<T>;
constructor(
collection: T[] | Compare<T> = [],
compare: Compare<T> = (l: T, r: T) => (l < r ? -1 : l > r ? 1 : 0),
) {
if (typeof collection === 'function') {
compare = collection;
collection = [];
}
this._size = 0;
this.compare = compare;
this.tree = new RBTree(compare);
for (const val of collection) this.add(val);
}
size(): number {
return this._size;
}
has(val: T): boolean {
return !!this.tree.find(val);
}
add(val: T): boolean {
const successful = this.tree.insert(val);
this._size += successful ? 1 : 0;
return successful;
}
delete(val: T): boolean {
const deleted = this.tree.deleteAll(val);
this._size -= deleted ? 1 : 0;
return deleted;
}
ceil(val: T): T | undefined {
let p = this.tree.root;
let higher = null;
while (p) {
if (this.compare(p.data, val) >= 0) {
higher = p;
p = p.left;
} else {
p = p.right;
}
}
return higher?.data;
}
floor(val: T): T | undefined {
let p = this.tree.root;
let lower = null;
while (p) {
if (this.compare(val, p.data) >= 0) {
lower = p;
p = p.right;
} else {
p = p.left;
}
}
return lower?.data;
}
higher(val: T): T | undefined {
let p = this.tree.root;
let higher = null;
while (p) {
if (this.compare(val, p.data) < 0) {
higher = p;
p = p.left;
} else {
p = p.right;
}
}
return higher?.data;
}
lower(val: T): T | undefined {
let p = this.tree.root;
let lower = null;
while (p) {
if (this.compare(p.data, val) < 0) {
lower = p;
p = p.right;
} else {
p = p.left;
}
}
return lower?.data;
}
first(): T | undefined {
return this.tree.inOrder().next().value;
}
last(): T | undefined {
return this.tree.reverseInOrder().next().value;
}
shift(): T | undefined {
const first = this.first();
if (first === undefined) return undefined;
this.delete(first);
return first;
}
pop(): T | undefined {
const last = this.last();
if (last === undefined) return undefined;
this.delete(last);
return last;
}
*[Symbol.iterator](): Generator<T, void, void> {
for (const val of this.values()) yield val;
}
*keys(): Generator<T, void, void> {
for (const val of this.values()) yield val;
}
*values(): Generator<T, undefined, void> {
for (const val of this.tree.inOrder()) yield val;
return undefined;
}
/**
* Return a generator for reverse order traversing the set
*/
*rvalues(): Generator<T, undefined, void> {
for (const val of this.tree.reverseInOrder()) yield val;
return undefined;
}
}
/**
* Your DinnerPlates object will be instantiated and called as such:
* var obj = new DinnerPlates(capacity)
* obj.push(val)
* var param_2 = obj.pop()
* var param_3 = obj.popAtStack(index)
*/type DinnerPlates struct {
capacity int
stacks [][]int
notFull *redblacktree.Tree
}
func Constructor(capacity int) DinnerPlates {
return DinnerPlates{capacity: capacity, notFull: redblacktree.NewWithIntComparator()}
}
func (this *DinnerPlates) Push(val int) {
if this.notFull.Size() == 0 {
this.stacks = append(this.stacks, []int{val})
if this.capacity > 1 {
this.notFull.Put(len(this.stacks)-1, nil)
}
} else {
index, _ := this.notFull.Left().Key.(int)
this.stacks[index] = append(this.stacks[index], val)
if len(this.stacks[index]) == this.capacity {
this.notFull.Remove(index)
}
}
}
func (this *DinnerPlates) Pop() int {
return this.PopAtStack(len(this.stacks) - 1)
}
func (this *DinnerPlates) PopAtStack(index int) int {
if index < 0 || index >= len(this.stacks) || len(this.stacks[index]) == 0 {
return -1
}
val := this.stacks[index][len(this.stacks[index])-1]
this.stacks[index] = this.stacks[index][:len(this.stacks[index])-1]
if index == len(this.stacks)-1 && len(this.stacks[index]) == 0 {
for len(this.stacks) > 0 && len(this.stacks[len(this.stacks)-1]) == 0 {
this.notFull.Remove(len(this.stacks) - 1)
this.stacks = this.stacks[:len(this.stacks)-1]
}
} else {
this.notFull.Put(index, nil)
}
return val
}
/**
* Your DinnerPlates object will be instantiated and called as such:
* obj := Constructor(capacity);
* obj.Push(val);
* param_2 := obj.Pop();
* param_3 := obj.PopAtStack(index);
*/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. |
| 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 | – |
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 |
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.