Dinner Plate Stacks - Problem

You have an infinite number of stacks arranged in a row and numbered (left to right) from 0. Each stack has the same maximum capacity.

Implement the DinnerPlates class:

  • DinnerPlates(int capacity) - Initializes the object with the maximum capacity of the stacks.
  • 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 stacks are empty.
  • int popAtStack(int index) - Returns the value at the top of the stack with the given index and removes it from that stack or returns -1 if the stack is empty.

Input & Output

Example 1 — Basic Operations
$ Input: Operations: ["DinnerPlates","push","push","push","push","pop","pop","pop","push","pop"], Values: [[2],[1],[2],[3],[4],[],[],[],[5],[]]
› Output: [null,null,null,null,null,2,1,-1,null,2]
💡 Note: Initialize with capacity 2, push 1,2,3,4 (creates stacks [[1,2],[3,4]]), pop returns 4,2,1, push 5 goes to first available spot, final pop returns 2
Example 2 — PopAtStack Usage
$ Input: Operations: ["DinnerPlates","push","push","popAtStack","push","pop"], Values: [[1],[1],[2],[0],[3],[]]
› Output: [null,null,null,1,null,3]
💡 Note: Capacity 1, push 1,2 creates [[1],[2]], popAtStack(0) removes 1, push 3 goes to stack 0, pop returns 3
Example 3 — Empty Stack Handling
$ Input: Operations: ["DinnerPlates","pop","push","pop","pop"], Values: [[2],[],[1],[],[]]
› Output: [null,-1,null,1,-1]
💡 Note: Pop from empty returns -1, push 1, pop returns 1, pop from empty again returns -1

Constraints

  • 1 ≤ capacity ≤ 2 × 104
  • 1 ≤ val ≤ 2 × 104
  • 0 ≤ index ≤ 105
  • At most 2 × 105 calls to push, pop, and popAtStack

Visualization

Tap to expand
Dinner Plate Stacks: Multiple Stack ManagementPush left→right, Pop right→left, Capacity=221Stack 043Stack 1PushPopOperations Resultpush(1) → Stack 0push(2) → Stack 0 (full)push(3) → Stack 1push(4) → Stack 1 (full)pop() → 4 (rightmost)Challenge: Efficiently find leftmost available and rightmost non-empty stacksSolution: Use heaps for O(log n) stack tracking
Understanding the Visualization
1
Input
Operations: push(1), push(2), push(3), push(4) with capacity=2
2
Process
Creates stacks: [[1,2], [3,4]] filling left to right
3
Output
Pop operations return from rightmost: 4, 2, 1
Key Takeaway
🎯 Key Insight: Use priority queues to efficiently track available stacks and rightmost positions for optimal performance

Related Problems

Asked in
Google 45 Amazon 38 Microsoft 32 Apple 28
28.5K Views
Medium Frequency
~35 min Avg. Time
892 Likes
Ln 1, Col 1
Smart Actions
💡 Explanation
AI Ready
💡 Suggestion Tab to accept Esc to dismiss
// Output will appear here after running code
Code Editor Closed
Click the red button to reopen