LeetCode Solutions Blog

Dinner Plate Stacks

Difficulty: Hard

Problem Description

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 with methods to push, pop, and pop at a specified stack index.

Key Insights

Each stack can hold a maximum number of plates defined by the capacity.
Plates should be added to the leftmost stack that is not full.
The rightmost non-empty stack should be the first to return plates on pop operations.
The implementation needs to handle edge cases where stacks may become empty or exceed the defined capacity.

Space and Time Complexity

Time Complexity:

push: O(1) on average, O(n) in the worst case if all stacks are full.
pop: O(1) on average, O(n) in the worst case if all stacks are empty.
popAtStack: O(1) on average, O(n) in the worst case if the specified stack is empty.

Space Complexity: O(n), where n is the number of plates pushed onto the stacks.

Solution

To efficiently manage the stacks, we can use a list to represent the stacks and a min-heap (priority queue) to keep track of the indices of stacks that are not full. The push method will always add plates to the leftmost available stack, while the pop method will remove plates from the rightmost non-empty stack. The popAtStack method allows for targeted removal from a specified stack.

Code Solutions

class DinnerPlates:
    def __init__(self, capacity: int):
        self.capacity = capacity  # Maximum capacity for each stack
        self.stacks = []  # List of stacks
        self.available = []  # Min-heap for storing indices of non-full stacks

    def push(self, val: int) -> None:
        # If there's an available stack, push to it
        if self.available:
            index = heapq.heappop(self.available)  # Get the leftmost non-full stack index
            if index >= len(self.stacks):
                self.stacks.append([])  # Extend the list of stacks if needed
            self.stacks[index].append(val)  # Push the plate onto the stack
            # If the stack is now full, do not push it back to available
            if len(self.stacks[index]) < self.capacity:
                heapq.heappush(self.available, index)
        else:
            # If no available stacks, create a new one
            self.stacks.append([val])  # Create a new stack with the plate
            if len(self.stacks[-1]) < self.capacity:
                heapq.heappush(self.available, len(self.stacks) - 1)

    def pop(self) -> int:
        # Pop from the rightmost non-empty stack
        while self.stacks and not self.stacks[-1]:  # Clear empty stacks from the end
            self.stacks.pop()
        if not self.stacks:
            return -1  # All stacks are empty
        return self.stacks[-1].pop()  # Remove and return the top plate

    def popAtStack(self, index: int) -> int:
        if index >= len(self.stacks) or not self.stacks[index]:
            return -1  # Specified stack is empty or does not exist
        plate = self.stacks[index].pop()  # Remove and return the top plate
        # If the stack is now not full, add it back to the available heap
        if len(self.stacks[index]) < self.capacity:
            heapq.heappush(self.available, index)
        return plate