Dinner Plate Stacks - Video Solutions

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.