Dinner Plate Stacks — LeetCode 1172 Python Solution
HardStackDesignHash TableHeap (Priority Queue)
- Problem
- #1172
- Pattern
- Heap / Priority Queue
- Reading time
- 7 min
- Source
- leetcode.com
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 stacks capacity.
Example
- Input
- ["DinnerPlates", "push", "push", "push", "push", "push", "popAtStack", "push", "push", "popAtStack", "popAtStack", "pop", "pop", "pop", "pop", "pop"]
- 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
Python solution
Python
class DinnerPlates:
def __init__(self, capacity: int):
self.capacity = capacity
self.stacks = []
self.not_full = SortedSet()
def push(self, val: int) -> None:
if not self.not_full:
self.stacks.append([val])
if self.capacity > 1:
self.not_full.add(len(self.stacks) - 1)
else:
index = self.not_full[0]
self.stacks[index].append(val)
if len(self.stacks[index]) == self.capacity:
self.not_full.discard(index)
def pop(self) -> int:
return self.popAtStack(len(self.stacks) - 1)
def popAtStack(self, index: int) -> int:
if index < 0 or index >= len(self.stacks) or not self.stacks[index]:
return -1
val = self.stacks[index].pop()
if index == len(self.stacks) - 1 and not self.stacks[-1]:
while self.stacks and not self.stacks[-1]:
self.not_full.discard(len(self.stacks) - 1)
self.stacks.pop()
else:
self.not_full.add(index)
return val
# Your DinnerPlates object will be instantiated and called as such:
# obj = DinnerPlates(capacity)
# obj.push(val)
# param_2 = obj.pop()
# param_3 = obj.popAtStack(index)Complexity
| Measure | Complexity |
|---|---|
| Time | (n \times \log n) |
| Space | O(n) auxiliary |
Pattern: Heap / Priority Queue
Keep only the best k elements, or always pull the smallest, in log time. LeetCode 1172. Dinner Plate Stacks is filed here because LeetCode tags it Heap (Priority Queue), which is the vocabulary this hub collects.
The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 1172. Dinner Plate Stacks?
- LeetCode 1172. Dinner Plate Stacks is rated Hard on LeetCode.
- What is the time complexity of LeetCode 1172. Dinner Plate Stacks?
- The Python solution on this page runs in (n \times \log n).
- What is the space complexity of LeetCode 1172. Dinner Plate Stacks?
- The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 1172. Dinner Plate Stacks cover?
- LeetCode 1172. Dinner Plate Stacks is tagged Stack, Design, Hash Table and Heap (Priority Queue) on LeetCode.