LeetCode Solutions Blog

Dinner Plate Stacks

Number: 1270

Difficulty: Hard

Paid? No

Companies: Amazon

Problem Description

Design a data structure that simulates an infinite number of stacks arranged in a row. Each stack has a fixed maximum capacity. Implement operations to push a value into the leftmost non-full stack, pop a value from the rightmost non-empty stack, and pop from a specific stack by index.

Key Insights

Use a min-heap to track indices of stacks that have available space for pushing new values.
Use a max-heap (or simply maintain an index pointer) to quickly find the rightmost non-empty stack for pop operations.
Lazy cleaning of heaps is necessary since indices stored might not always reflect the current state after removals.
Maintain an array (or list) of stacks to store the elements and update available stacks as elements are pushed or popped.

Space and Time Complexity

Time Complexity:

push: O(log n) per operation (due to heap operations)
pop/popAtStack: O(log n) per operation (worst-case heap adjustments)

Space Complexity:

O(n) where n is the number of stacks created, plus additional space for heap storage.

Solution

The solution uses two heaps and an array of stacks:

A min-heap tracks stack indices that are not yet full. When pushing a value, we pop from this heap to find the leftmost available stack. If the heap index is outdated (i.e. the stack is already full), we discard it and try the next available index.
For popping from any specific stack (popAtStack), we simply check if the given stack is not empty and update the available space heap accordingly.
For the pop operation, we maintain a pointer to the rightmost stack that is non-empty (or use a max-heap) and perform a lazy cleanup to skip empty stacks.

Whenever a push or pop operation changes a stack from full to not full (or vice versa), we add that stack index to the min-heap. This keeps our structure updated and allows efficient retrieval of the target stacks for each operation.

Code Solutions

import heapq

class DinnerPlates:
    def __init__(self, capacity: int):
        # capacity of each stack
        self.capacity = capacity
        # list of stacks
        self.stacks = []
        # min-heap to store indices of stacks that are not full
        self.available = []
        # pointer for the rightmost non-empty stack
        self.rightmost = -1

    def push(self, val: int) -> None:
        # Ensure the available heap is valid
        while self.available and self.available[0] < len(self.stacks) and len(self.stacks[self.available[0]]) == self.capacity:
            heapq.heappop(self.available)
        # If there is no available stack, append a new one
        if not self.available:
            heapq.heappush(self.available, len(self.stacks))
            self.stacks.append([])
        # Choose the leftmost stack from available heap and push into it
        index = self.available[0]
        self.stacks[index].append(val)
        # If stack becomes full, pop it from available
        if len(self.stacks[index]) == self.capacity:
            heapq.heappop(self.available)
        # Update rightmost index if needed
        self.rightmost = max(self.rightmost, index)

    def pop(self) -> int:
        # Pop from the rightmost non-empty stack
        while self.rightmost >= 0 and (self.rightmost >= len(self.stacks) or not self.stacks[self.rightmost]):
            self.rightmost -= 1
        if self.rightmost < 0:
            return -1
        val = self.stacks[self.rightmost].pop()
        # Add this index back into available heap as it now has space
        heapq.heappush(self.available, self.rightmost)
        return val

    def popAtStack(self, index: int) -> int:
        # If index is out of range or the stack is empty
        if index >= len(self.stacks) or not self.stacks[index]:
            return -1
        val = self.stacks[index].pop()
        # Add the index to available since there's now space (even if it might have been recorded)
        heapq.heappush(self.available, index)
        # Optionally update rightmost pointer if needed
        if index == self.rightmost and not self.stacks[index]:
            while self.rightmost >= 0 and (self.rightmost >= len(self.stacks) or not self.stacks[self.rightmost]):
                self.rightmost -= 1
        return val