Dinner Plate Stacks

Hard

Asked by:

3 views

Topics:

StacksArraysGreedy AlgorithmsDynamic Programming

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

Example 1:

Input
["DinnerPlates", "push", "push", "push", "push", "push", "popAtStack", "push", "push", "popAtStack", "popAtStack", "pop", "pop", "pop", "pop", "pop"]
[[2], [1], [2], [3], [4], [5], [0], [20], [21], [0], [2], [], [], [], [], []]
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
D.push(1);
D.push(2);
D.push(3);
D.push(4);
D.push(5);         // The stacks are now:  2  4
                                           1  3  5
                                           ﹈ ﹈ ﹈
D.popAtStack(0);   // Returns 2.  The stacks are now:     4
                                                       1  3  5
                                                       ﹈ ﹈ ﹈
D.push(20);        // The stacks are now: 20  4
                                           1  3  5
                                           ﹈ ﹈ ﹈
D.push(21);        // The stacks are now: 20  4 21
                                           1  3  5
                                           ﹈ ﹈ ﹈
D.popAtStack(0);   // Returns 20.  The stacks are now:     4 21
                                                        1  3  5
                                                        ﹈ ﹈ ﹈
D.popAtStack(2);   // Returns 21.  The stacks are now:     4
                                                        1  3  5
                                                        ﹈ ﹈ ﹈ 
D.pop()            // Returns 5.  The stacks are now:      4
                                                        1  3 
                                                        ﹈ ﹈  
D.pop()            // Returns 4.  The stacks are now:   1  3 
                                                        ﹈ ﹈   
D.pop()            // Returns 3.  The stacks are now:   1 
                                                        ﹈   
D.pop()            // Returns 1.  There are no stacks.
D.pop()            // Returns -1.  There are still no stacks.

Constraints:

1 <= capacity <= 2 * 10⁴
1 <= val <= 2 * 10⁴
0 <= index <= 10⁵
At most 2 * 10⁵ calls will be made to push, pop, and popAtStack.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the maximum values for `capacity` and the input values passed to `push`? Are there any limits to the number of `push` or `popAtStack` calls?
If `popAtStack` is called with an index that is out of bounds or an empty stack, what should the method return?
Is the `index` passed to `popAtStack` guaranteed to be a valid stack index that was previously created by a `push` operation?
If `pop` is called when all stacks are empty, what should the method return?
Can `capacity` be zero? If so, how should the class behave?

Brute Force Solution

Approach

We need to simulate a collection of stacks that act like dinner plates, where each stack has a limited capacity. The brute force approach simply tries to perform each push and pop operation as requested, checking all possible stacks to find the correct one.

Here's how the algorithm would work step-by-step:

For each 'push' operation, go through all the stacks from left to right.
If a stack isn't full, put the new plate (value) on that stack.
If all the stacks are full, create a new stack and put the plate on that new stack.
For each 'pop' operation, go through the stacks from right to left.
If a stack isn't empty, take the top plate (value) off that stack and return it.
If all the stacks are empty, there is nothing to pop, return -1.
For each 'popAtStack' operation, find the specified stack.
If the specified stack isn't empty, take the top plate (value) off that stack and return it.
If the specified stack is empty, there is nothing to pop, return -1.

Code Implementation

class DinnerPlates:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.stacks_list = []

    def push(self, val: int) -> None:
        # Iterate through the stacks to find the first non-full stack
        for stack in self.stacks_list:
            if len(stack) < self.capacity:
                stack.append(val)
                return

        # If all stacks are full, create a new stack.
        self.stacks_list.append([val])

    def pop(self) -> int:
        # Iterate through the stacks from right to left.
        for i in range(len(self.stacks_list) - 1, -1, -1):
            if self.stacks_list[i]:
                return self.stacks_list[i].pop()

        # If all stacks are empty, return -1.
        return -1

    def popAtStack(self, index: int) -> int:
        # Check if the index is valid
        if 0 <= index < len(self.stacks_list) and self.stacks_list[index]:
            # If the stack isn't empty, pop the top element.
            return self.stacks_list[index].pop()
        else:
            # If the stack is empty or index invalid, return -1.
            return -1

Big(O) Analysis

Time Complexity

O(n) – In the worst-case scenario, the push operation may need to iterate through all existing stacks to find a non-full stack, which takes O(n) time, where n is the number of stacks. Similarly, the pop operation could require iterating through all stacks to find a non-empty stack, also taking O(n) time. The popAtStack operation directly accesses the stack at the given index and performs a pop operation which takes O(1) time. Since the dominant operations (push and pop) can take O(n) time, the overall time complexity is O(n).

Space Complexity

O(N) – The primary space consumption comes from storing the stacks of dinner plates. In the worst-case scenario, where each push operation creates a new stack (especially if the capacity is 1), we could end up with N stacks after N push operations, where N is the number of push operations. Each stack stores plates, so the total number of plates stored across all stacks can be N as well. Therefore, the auxiliary space used to store the stacks grows linearly with the number of push operations, leading to a space complexity of O(N).

Optimal Solution

Approach

Imagine managing stacks of plates where you want to keep adding and removing plates efficiently. The trick is to keep track of where you have space to add plates and where you can easily remove them, avoiding full or empty stacks as much as possible.

Here's how the algorithm would work step-by-step:

Keep a list of the stacks that have available space.
When adding a plate, first check if there is any stack with available space. If there is, put the plate there. If not, create a new stack and put the plate in it.
Maintain a list of the stacks that are not empty so you know where you can remove a plate from.
When removing a plate, take it from the stack at the end of your list that isn't empty.
When a stack becomes full after adding a plate, remove it from the list of stacks with available space.
When a stack becomes empty after removing a plate, remove it from the list of stacks that are not empty.
By managing those lists, you'll always know where to add and remove plates quickly, without wasting time searching through stacks.

Code Implementation

class DinnerPlates:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.stacks = []
        self.available_stacks = []

    def push(self, value: int) -> None:
        # Find an available stack or create a new one
        if self.available_stacks:
            index_to_use = self.available_stacks[0]
            self.stacks[index_to_use].append(value)
            if len(self.stacks[index_to_use]) == self.capacity:
                self.available_stacks.pop(0)
        else:
            self.stacks.append([value])
            if len(self.stacks[-1]) < self.capacity:
                self.available_stacks.append(len(self.stacks) - 1)

    def pop(self) -> int:
        # Pop from the rightmost non-empty stack
        while self.stacks and not self.stacks[-1]:
            self.stacks.pop()

        if not self.stacks:
            return -1

        value_to_return = self.stacks[-1].pop()

        if len(self.stacks[-1]) == 0:
            self.stacks.pop()

        # Re-add to available stacks if applicable
        if self.stacks and len(self.stacks[-1]) < self.capacity:
            if not self.available_stacks or self.available_stacks[-1] != len(self.stacks) -1:
                self.available_stacks.append(len(self.stacks) - 1)
                self.available_stacks.sort()

        return value_to_return

    def popAtStack(self, index: int) -> int:
        if index >= len(self.stacks) or not self.stacks[index]:
            return -1

        value_to_return = self.stacks[index].pop()

        # Keep track of available stack
        if index not in self.available_stacks:
            self.available_stacks.append(index)
            self.available_stacks.sort()

        # Clean up trailing empty stacks
        while self.stacks and not self.stacks[-1]:
            self.stacks.pop()

        return value_to_return

# Your DinnerPlates object will be instantiated and called as such:
# dinner_plates_object = DinnerPlates(capacity)
# dinner_plates_object.push(value)
# value_popped = dinner_plates_object.pop()
# value_popped_at_stack = dinner_plates_object.popAtStack(index)

Big(O) Analysis

Time Complexity

O(log n) – The push operation involves potentially adding to a priority queue (or similar sorted data structure) of available stacks and could involve creating a new stack at the end, which is typically O(log n) for priority queue operations. The pop operation relies on the priority queue to find the appropriate stack, also O(log n). The complexity is dominated by operations on the priority queue, which maintains stacks sorted by index to find the leftmost available or rightmost non-empty stack. Therefore, the amortized time complexity for both push and pop operations is O(log n).

Space Complexity

O(N) – The provided solution maintains a list of stacks, which in the worst case could contain N stacks, where N is the maximum number of plates that can be held across all stacks. Additionally, it keeps lists of stacks with available space and non-empty stacks, both of which could also potentially grow to a size proportional to N. Therefore, the auxiliary space used by these lists is O(N).

Edge Cases

Case	How to Handle
pushing to a full stack	The algorithm should create a new stack if the current stack is full, adding it to the available stacks.
popping from an empty stack	If all stacks are empty when popping, the algorithm should return -1.
popping from the overall DinnerPlateStacks when no stacks are present	If no stacks have ever been added, or they have all been popped, return -1.
Capacity is zero or negative	Throw an IllegalArgumentException or return an error code as an invalid capacity.
pushing and popping from stacks that become empty and need to be removed	The algorithm needs to efficiently track the leftmost non-empty and rightmost non-full stacks and update them after pushes and pops.
repeated pushing and popping that cause excessive stack creation and deletion	The algorithm should aim for creating new stacks only when needed and reusing or cleaning up the empty stacks to avoid memory leaks.
attempting to popAt an invalid index (index out of bounds)	The algorithm should check if the index is within the bounds of the list of stacks and handle the case gracefully, potentially returning -1 or throwing an exception.
popAt from an empty stack at a valid index	If the stack at index is empty return -1, indicating no value can be popped.

pushing to a full stack

How to Handle:

The algorithm should create a new stack if the current stack is full, adding it to the available stacks.

popping from an empty stack

How to Handle:

If all stacks are empty when popping, the algorithm should return -1.

popping from the overall DinnerPlateStacks when no stacks are present

How to Handle:

If no stacks have ever been added, or they have all been popped, return -1.

Capacity is zero or negative

How to Handle:

Throw an IllegalArgumentException or return an error code as an invalid capacity.

pushing and popping from stacks that become empty and need to be removed

How to Handle:

The algorithm needs to efficiently track the leftmost non-empty and rightmost non-full stacks and update them after pushes and pops.

repeated pushing and popping that cause excessive stack creation and deletion

How to Handle:

The algorithm should aim for creating new stacks only when needed and reusing or cleaning up the empty stacks to avoid memory leaks.

attempting to popAt an invalid index (index out of bounds)

How to Handle:

The algorithm should check if the index is within the bounds of the list of stacks and handle the case gracefully, potentially returning -1 or throwing an exception.

popAt from an empty stack at a valid index

How to Handle:

If the stack at index is empty return -1, indicating no value can be popped.