1172. Dinner Plate Stacks

1172

HardData Structure DesignArray of stacks plus a min-heap for the leftmost open slotList of stacks with a min-heap of available (non-full) stack indices

Dinner Plate Stacks

Design DinnerPlates with a fixed capacity per stack. push(val) places the value on the leftmost stack that is not full (creating a new rightmost stack if all are full). pop() removes and returns the value from the rightmost non-empty stack, or -1 if all are empty. popAtStack(index) removes and returns the top of the stack at the given index, or -1 if that stack is empty or does not exist.

Open official problem prompt ↗

In plain English

Route each push to the leftmost stack with free space and each pop to the rightmost non-empty stack, even as middle stacks empty and refill.

Picture it like this

A cafeteria counter of plate dispensers, each holding a fixed number of plates. Diners take from the far-right dispenser, but a busboy always refills the leftmost one that has room; a directory of which dispensers have space keeps refilling fast.

Example

Input: DinnerPlates(2); push(1); push(2); push(3); push(4); push(5); popAtStack(0); push(20); push(21); popAtStack(0); popAtStack(2); pop(); pop(); pop(); pop(); pop()
Output: [null, null, null, null, null, null, 2, null, null, 20, 21, 5, 4, 3, 1, -1]
Why: Capacity 2 gives stacks [1,2],[3,4],[5]; popAtStack(0) returns 2 freeing a left slot, so push(20) refills stack 0 and push(21) fills stack 2; the popAtStacks return 20 and 21; then pops peel from the right: 5,4,3,1, and finally -1 when empty.

Constraints

1 <= capacity <= 2 * 10^41 <= val <= 2 * 10^40 <= index < number of stacks that have ever existedAt most 2 * 10^5 calls to push, pop, and popAtStack

Pattern lesson

See the pattern, then code

List of stacks with a min-heap of available (non-full) stack indices

↗

Data Structure Design

An API whose operations must meet strict O(1) or O(log n) contracts.. Keep the stacks in a list. A min-heap of indices that currently have free space lets push grab the smallest open index in log time; popAtStack pushes an index back onto that heap when it frees a slot. pop just trims trailing empty stacks and pops the last.

New words, made simpleKnow these before the algorithm

Available heap: A min-heap of stack indices that currently have free space, so push finds the leftmost opening in log time.
Stale heap entry: An index in the heap that is now full or out of range; discarded lazily on push.
Trailing empty trim: Dropping empty stacks off the right end so pop targets a real non-empty stack.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Scan for leftmost non-full stack

Linear scans across up to 2*10^5 operations time out.

On each push, linearly scan stacks from the left to find room.

Time O(n) per pushSpace O(n)

Best choiceList of stacks + min-heap of open indices

Leftmost-open lookups become logarithmic and stay correct as middles empty.

Track available indices in a min-heap; reinsert an index whenever popAtStack frees a slot.

Time O(log n) push/popAtStackSpace O(n)

The rule we keep true

Invariant

The heap contains every stack index that has free capacity (possibly with stale extras that are pruned lazily), and stacks[-1] is trimmed to be non-empty before pop reads it.

Why this is correct

Reasoning

push always consumes the heap's minimum valid index, which is by definition the leftmost stack with room; popAtStack re-adds an index the moment it frees a slot, so no opening is ever lost. Stale entries are harmless because push validates the heap top before using it, and each index enters/leaves the heap O(1) times per freed slot, giving amortized log cost.

The algorithm in three movesSay these aloud before coding

1Store stacks in a list and a min-heap of indices that have room

push 1..5 -> stacks=[[1,2],[3,4],[5]] avail=[2]

2On push, discard stale heap tops (out of range or full), create a new stack if the heap is empty, then push onto the smallest available index and remove it if it becomes full

popAtStack(0)=2 -> stacks[0]=[1] avail=[0,2]

3On popAtStack(index), if valid pop its top and push that index back onto the available heap

push(20) -> leftmost open idx 0 -> stacks[0]=[1,20]

4On pop, drop trailing empty stacks, then popAtStack on the last remaining index

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

[1,2]0

[3,4]1

[5]2

1 · Read1,2,3,4,5

2 · AskWhere does each go?

3 · Update statestacks=[[1,2],[3,4],[5]], avail=[2]

4 · Resultstacks 0,1 fill, 5 opens stack 2

Key takeaway

Three capacity-2 stacks; the min-heap of available indices routes each push to the leftmost stack with room.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 4-7State
stacks holds the plate columns; avail is the min-heap of indices with room.
2
Lines 9-11Prune stale openings
Discard heap indices that are out of range or already full before trusting the top.
3
Lines 12-18push placement
Create a new rightmost stack if none is open, then push onto the leftmost open index and evict it from the heap when it fills.
4
Lines 20-25pop with trailing trim
Remove empty stacks off the right so pop always acts on a genuinely non-empty last stack.
5
Lines 27-31popAtStack re-opens a slot
A valid pop frees a slot, so its index goes back on the available heap for future pushes.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

popAtStack on an index that exists but is empty (returns -1)
popAtStack on an out-of-range index (returns -1)
pop when every stack is empty (returns -1)
capacity 1 so each stack holds exactly one element
push after a middle stack was emptied must refill that middle, not a new right stack

Common beginner mistakes

Not pruning stale (full or out-of-range) indices from the heap before using the top, sending a push to a full stack
Forgetting to push the index back onto avail in popAtStack, so freed middle slots are never reused
pop reading stacks[-1] without trimming trailing empty stacks first
Leaving grown-then-emptied stacks in the list so indices drift (must lazily trim on pop)

Check your understanding

Why is a min-heap the right structure for finding where push should go?

PyPython 3 · solution.py

Optimal

1import heapq23class DinnerPlates:4    def __init__(self, capacity: int):5        self.cap = capacity6        self.stacks = []7        self.avail = []89    def push(self, val: int) -> None:10        while self.avail and (self.avail[0] >= len(self.stacks) or len(self.stacks[self.avail[0]]) >= self.cap):11            heapq.heappop(self.avail)12        if not self.avail:13            self.stacks.append([])14            heapq.heappush(self.avail, len(self.stacks) - 1)15        idx = self.avail[0]16        self.stacks[idx].append(val)17        if len(self.stacks[idx]) >= self.cap:18            heapq.heappop(self.avail)1920    def pop(self) -> int:21        while self.stacks and not self.stacks[-1]:22            self.stacks.pop()23        if not self.stacks:24            return -125        return self.popAtStack(len(self.stacks) - 1)2627    def popAtStack(self, index: int) -> int:28        if index < 0 or index >= len(self.stacks) or not self.stacks[index]:29            return -130        heapq.heappush(self.avail, index)31        return self.stacks[index].pop()

Time complexityO(log n) amortized per push and popAtStack; O(1) amortized per popOptimized

Space complexityO(total elements + number of stacks)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonGoogleUber

Dinner Plate Stacks

Dinner Plate Stacks

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Data Structure Design