Facebook Pixel

1172. Dinner Plate Stacks


Problem Description

In the given LeetCode problem, we are asked to implement a class named DinnerPlates to manage a series of stacks with a specified maximum capacity. The stacks are infinite and numbered starting from 0. They behave a bit differently than regular stacks in that when pushing an element, it must be placed in the leftmost stack that is not already full. Similarly, when popping an element without specifying a stack, the value comes from the rightmost non-empty stack.

The class requires the following functions:

  • DinnerPlates(int capacity): Constructor that initialises stacks with a given capacity.
  • void push(int val): Adds the value val to the leftmost stack with space available.
  • int pop(): Removes and returns the value from the top of the rightmost non-empty stack or returns -1 if all stacks are empty.
  • int popAtStack(int index): Removes and returns the value from the top of the stack at the given index or returns -1 if the specified stack is empty.

This problem tests the implementation of a dynamic system of stacks with specific pushing and popping rules.

Intuition

The solution requires efficiently managing both the leftmost non-full stack for pushing and the rightmost non-empty stack for popping. Using a dynamic array (list in Python) to simulate stacks is natural since we can append and remove elements from the end.

We need a way to quickly access the leftmost non-full stack when pushing. If we were to scan every time we wanted to push, the operation would become inefficient (think linear time complexity), as stacks grow. For this reason, the solution employs a SortedSet to keep track of stacks that are not full. Why a sorted set? Because it maintains the order and allows us to access the smallest index quickly, which corresponds to the leftmost non-full stack.

For popping elements from the rightmost non-empty stack, we simply look at the last stack and pop from there. If the pop is called with a specific stack index, we also need to check if the stack at that index is empty or not. If it's not empty, we pop from there. If a pop operation results in a previously full stack no longer being full, we need to add that stack's index to not_full to reflect that it now has space.

Moreover, whenever we pop an element, we also need to handle the scenario of possibly empty stacks left at the end after popping. In such cases, those stacks should be removed since they're now redundant, and their indices should be removed from the not_full set if they're present there.

The provided Python code implements this logic, ensuring efficient operations by strategically using a SortedSet for tracking and array operations for regular stack behavior.

Learn more about Stack and Heap (Priority Queue) patterns.

Solution Approach

The DinnerPlates class is designed with a combination of a dynamic array (self.stacks) and a sorted set (self.not_full) to manage the collection of stacks and efficiently perform the required operations. Here's how each method works and what algorithms and data structures they utilize:

  1. __init__(self, capacity: int): The constructor initializes the object with a specified capacity for each stack. self.stacks is the dynamic array that holds stacks, where each stack is itself represented as a list. self.not_full is a SortedSet, which is part of the sortedcontainers module. This set will keep track of the indices of stacks that aren't full.

  2. push(self, val: int): This method handles adding a new element to the stacks. If self.not_full is empty, it means there are no partially filled stacks, and we need to create a new stack (list). We append [val] to self.stacks. If there is room for more elements (capacity greater than 1), the index of the new stack is added to self.not_full. If self.not_full is not empty, we fetch the index of the leftmost non-full stack (self.not_full[0]), push val to that stack, and check if it becomes full. If it does, the index is removed from self.not_full.

  3. pop(self): Popping from the rightmost non-empty stack is equivalent to popping at the index of the last stack in self.stacks, so this method simply calls popAtStack with len(self.stacks) - 1.

  4. popAtStack(self, index): This method pops the value from a given index. It first checks if the index is valid and the stack at that index is not empty. If any conditions are unmet, it returns -1. Otherwise, it pops the element from the specified stack. If popping the element results in an empty stack at the rightmost position, it removes the empty stacks from the end of self.stacks and updates self.not_full. If the popped stack isn't completely empty, it adds the index to self.not_full since the stack now has room for more elements.

The approach handles edge cases, such as ensuring 'push' does not add to a full stack and 'pop' operations properly manage the dynamic size of self.stacks. Each operation is optimized to ensure constant-time complexity, except the pop at an arbitrary stack which may lead to linear time due to the need to shrink the array if the operation results in empty stack(s) at the end. Overall, the solution efficiently utilizes a combination of stack-like behavior with ordered index tracking.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach for the DinnerPlates class. Suppose we initialize DinnerPlates with a capacity of 2.

  1. Initialize the DinnerPlates object:

    dinner_plates = DinnerPlates(2)

    self.stacks = [] self.not_full = SortedSet()

  2. Push some elements:

    dinner_plates.push(1)

    self.stacks now looks like [[1]], self.not_full will be {0} because the first stack is not full.

    Again, push another element:

    dinner_plates.push(2)

    self.stacks is now [[1, 2]], self.not_full becomes empty, {}, as the first stack is now full.

    Push one more element:

    dinner_plates.push(3)

    A new stack gets created, and the element is added to it, so self.stacks becomes [[1, 2], [3]]. The self.not_full set is updated to {1}, indicating that the second stack has space left.

  3. Pop from the rightmost non-empty stack:

    val = dinner_plates.pop()

    This pops 3 from the second stack, self.stacks is now [[1, 2], []]. Since we have an empty stack at the end, we remove it, resulting in: self.stacks = [[1, 2]]. The self.not_full set should remain empty because no non-full stacks are available.

  4. Pop from a specific stack:

    val = dinner_plates.popAtStack(0)

    This will pop 2 from the first stack, self.stacks remains as [[1]]. Now, this makes stack 0 not full, so self.not_full is now {0}.

  5. Push another element:

    dinner_plates.push(4)

    Since there's a non-full stack available (stack 0), self.stacks becomes [[1, 4]] and self.not_full is empty again, because stack 0 is now full.

Through this example, we can see how the DinnerPlates class efficiently manages the stack operations based on the given conditions. The self.not_full sorted set allows quickly finding the leftmost non-full stack for push operations and maintaining order without the need for a linear scan every time. Popping elements updates self.stacks and the self.not_full data structures as necessary to reflect the current state of the stacks.

Solution Implementation

1from sortedcontainers import SortedSet
2
3class DinnerPlates:
4    def __init__(self, capacity: int):
5        self.capacity = capacity   # Maximum capacity of a stack
6        self.stacks = []           # List to hold the stacks
7        self.partially_full = SortedSet()  # Sorted set to keep track of non-full stacks
8
9    def push(self, val: int) -> None:
10        # If there is no partially full stack, create a new one and add the value.
11        if not self.partially_full:
12            self.stacks.append([val])
13            # If capacity is greater than 1, add the new stack's index to partially full.
14            if self.capacity > 1:
15                self.partially_full.add(len(self.stacks) - 1)
16        else:
17            # Find the index of the first non-full stack and push the value onto it.
18            index = self.partially_full[0]
19            self.stacks[index].append(val)
20            # If stack becomes full, remove from the partially full set.
21            if len(self.stacks[index]) == self.capacity:
22                self.partially_full.discard(index)
23
24    def pop(self) -> int:
25        # Pop a value from the last stack.
26        return self.pop_at_stack(len(self.stacks) - 1)
27
28    def pop_at_stack(self, index: int) -> int:
29        # If index is out of range or the stack is empty, return -1.
30        if index < 0 or index >= len(self.stacks) or not self.stacks[index]:
31            return -1
32        # Pop the value from the specified stack.
33        val = self.stacks[index].pop()
34        # If the last stack becomes empty, remove it and update the partially full set.
35        if index == len(self.stacks) - 1 and not self.stacks[-1]:
36            while self.stacks and not self.stacks[-1]:
37                self.partially_full.discard(len(self.stacks) - 1)
38                self.stacks.pop()
39        else:
40            # If the stack is still non-empty after pop, mark it as partially full.
41            self.partially_full.add(index)
42        return val
43
44
45# Example usage:
46# dinner_plates = DinnerPlates(capacity=3)
47# dinner_plates.push(1)
48# dinner_plates.push(2)
49# dinner_plates.push(3)
50# dinner_plates.push(4)
51# top_val = dinner_plates.pop()  # Should return 4
52# top_val_at_stack = dinner_plates.pop_at_stack(0)  # Should return 3
53
1import java.util.ArrayDeque;
2import java.util.ArrayList;
3import java.util.Deque;
4import java.util.List;
5import java.util.TreeSet;
6
7class DinnerPlates {
8    // Capacity of each stack.
9    private int capacity;
10  
11    // List of stacks to hold dinner plates. Each stack is a double-ended queue to allow for popping from both ends.
12    private List<Deque<Integer>> stacks;
13  
14    // Set to keep track of stacks that are not full, organized in ascending order by their indices.
15    private TreeSet<Integer> notFull;
16
17    // Constructor initializes stacks and the set for tracking non-full stacks.
18    public DinnerPlates(int capacity) {
19        this.capacity = capacity;
20        this.stacks = new ArrayList<>();
21        this.notFull = new TreeSet<>();
22    }
23
24    // Method to push a plate on top of the available stack.
25    // If all the stacks are full, creates a new stack for the plate.
26    public void push(int val) {
27        if (notFull.isEmpty()) {
28            Deque<Integer> newStack = new ArrayDeque<>();
29            newStack.push(val);
30            stacks.add(newStack);
31            // If capacity allows, add the new stack's index to notFull set because it's not full yet.
32            if (capacity > 1) {
33                notFull.add(stacks.size() - 1);
34            }
35        } else {
36            // Get the index of the first non-full stack.
37            int index = notFull.first();
38            stacks.get(index).push(val);
39            // If the selected stack is now full, remove it from the notFull set.
40            if (stacks.get(index).size() == capacity) {
41                notFull.pollFirst();
42            }
43        }
44    }
45
46    // Method to pop a plate from the last stack.
47    // Delegates to popAtStack method using index of the last stack.
48    public int pop() {
49        return popAtStack(stacks.size() - 1);
50    }
51
52    // Method to pop a plate from a specific stack given by an index.
53    // Returns -1 if the index is invalid or the stack is empty.
54    public int popAtStack(int index) {
55        // Check for invalid index or empty stack.
56        if (index < 0 || index >= stacks.size() || stacks.get(index).isEmpty()) {
57            return -1;
58        }
59        // Pop the top plate from the specified stack.
60        int val = stacks.get(index).pop();
61        // If it was the last plate in the last stack, remove the empty stack.
62        if (index == stacks.size() - 1 && stacks.get(index).isEmpty()) {
63            while (!stacks.isEmpty() && stacks.get(stacks.size() - 1).isEmpty()) {
64                notFull.remove(stacks.size() - 1);
65                stacks.remove(stacks.size() - 1);
66            }
67        } else {
68            // If the stack is not empty, add its index to the notFull set as it has space available now.
69            notFull.add(index);
70        }
71        return val;
72    }
73}
74
75/**
76 * The above class DinnerPlates demonstrates how to use a combination of ArrayList and TreeSet to efficiently manage a set
77 * of stacks with a fixed individual capacity.
78 * The main operations are push, which adds a plate to a stack, and pop, which removes a plate from a stack.
79 * There's also a popAtStack method that allows popping from a specified stack.
80 * The TreeSet notFull helps find the correct stack to push new plates onto.
81 */
82
1#include <vector>
2#include <stack>
3#include <set>
4using namespace std;
5
6class DinnerPlates {
7public:
8    // Constructor that sets the capacity for each stack.
9    DinnerPlates(int capacity) : capacity_(capacity) {}
10
11    // Pushes a value onto the last stack that has not reached capacity or onto a new stack if necessary.
12    void push(int val) {
13        // If there are no stacks with space available, create a new one
14        if (not_full_stacks_.empty()) {
15            stacks_.emplace_back(); // Create a new stack
16            stacks_.back().push(val); // Push the value onto the new stack
17            // If the stack's capacity is greater than one, add the new stack to the set of not full stacks
18            if (capacity_ > 1) {
19                not_full_stacks_.insert(stacks_.size() - 1);
20            }
21        } else {
22            // Otherwise, push the value onto a stack that's not yet full
23            int index = *not_full_stacks_.begin();
24            stacks_[index].push(val);
25            // If the stack is now full, remove it from the set of not full stacks
26            if (stacks_[index].size() == capacity_) {
27                not_full_stacks_.erase(index);
28            }
29        }
30    }
31
32    // Pops a value from the last non-empty stack.
33    int pop() {
34        return popAtStack(static_cast<int>(stacks_.size()) - 1);
35    }
36
37    // Pops a value from the specified stack.
38    int popAtStack(int index) {
39        // Check if the index is out of bounds or the stack is empty
40        if (index < 0 || index >= stacks_.size() || stacks_[index].empty()) {
41            return -1;
42        }
43        // Pop the value from the specified stack
44        int val = stacks_[index].top();
45        stacks_[index].pop();
46        // If popping the value leaves the stack empty and it's the last stack, remove empty stacks from the back
47        if (index == stacks_.size() - 1 && stacks_[index].empty()) {
48            while (!stacks_.empty() && stacks_.back().empty()) {
49                not_full_stacks_.erase(stacks_.size() - 1);
50                stacks_.pop_back();
51            }
52        } else {
53            // Otherwise, add the stack index back to the set of not full stacks
54            not_full_stacks_.insert(index);
55        }
56        return val;
57    }
58
59private:
60    int capacity_; // The capacity of each stack
61    vector<stack<int>> stacks_; // A dynamic array of stacks to store the plates
62    set<int> not_full_stacks_; // A set to keep track of stacks that are not yet full
63};
64
65/**
66 * Your DinnerPlates object will be instantiated and called as such:
67 * DinnerPlates* obj = new DinnerPlates(capacity);
68 * obj->push(val);
69 * int param_2 = obj->pop();
70 * int param_3 = obj->popAtStack(index);
71 */
72
1let capacity: number;
2let stacks: number[][];
3let notFull: TreeSet<number>;
4
5function initializeDinnerPlates(c: number): void {
6    capacity = c;
7    stacks = [];
8    notFull = new TreeSet<number>();
9}
10
11function pushToDinnerPlate(val: number): void {
12    if (notFull.size() === 0) {
13        stacks.push([val]);
14        if (capacity > 1) {
15            notFull.add(stacks.length - 1);
16        }
17    } else {
18        const index = notFull.first()!;