1172. Dinner Plate Stacks

HardStackDesignHash TableHeap (Priority Queue)
Leetcode Link

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

A heap is a ...?

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which data structure is used to implement priority queue?

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:

    1dinner_plates = DinnerPlates(2)

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

  2. Push some elements:

    1dinner_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:

    1dinner_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:

    1dinner_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:

    1val = 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:

    1val = 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:

    1dinner_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()!;
19        stacks[index].push(val);
20        if (stacks[index].length === capacity) {
21            notFull.delete(index);
22        }
23    }
24}
25
26function popFromDinnerPlate(): number {
27    return popAtStackDinnerPlate(stacks.length - 1);
28}
29
30function popAtStackDinnerPlate(index: number): number {
31    if (index < 0 || index >= stacks.length || stacks[index].length === 0) {
32        return -1;
33    }
34    const val = stacks[index].pop()!;
35    if (index === stacks.length - 1 && stacks[index].length === 0) {
36        while (stacks.length > 0 && stacks[stacks.length - 1].length === 0) {
37            notFull.delete(stacks.length - 1);
38            stacks.pop();
39        }
40    } else {
41        notFull.add(index);
42    }
43    return val;
44}
45
46// Red-Black Tree node structure.
47class RBTreeNode<T = number> {
48    // other RBTreeNode methods and properties
49}
50
51// Red-Black Tree methods for global usage.
52function rotateLeft(/* arguments */) {
53    // logic for left rotation
54}
55
56function rotateRight(/* arguments */) {
57    // logic for right rotation
58}
59
60// ... Continue with additional global methods for the RBTree functionality
61
62// Red Black Tree implementation with global functions and encapsulation of tree logic.
63class RBTree<T> { 
64    // RBTree methods and properties
65}
66
67// TreeSet implementation as a global collection
68let size: number;
69let tree: RBTree<number>;
70const lt: (a: number, b: number) => boolean;
71
72function initializeTreeSet(comparator: (l: number, r: number) => number): void {
73    size = 0;
74    tree = new RBTree<number>(comparator);
75    lt = (a: number, b: number) => comparator(a, b) < 0;
76}
77
78function hasInTreeSet(val: number): boolean {
79    // logic to check presence in TreeSet
80}
81
82function addInTreeSet(val: number): boolean {
83    // logic to add element in TreeSet
84}
85
86function deleteInTreeSet(val: number): boolean {
87    // logic to delete element from TreeSet
88}
89
90function ceilingInTreeSet(val: number): number | undefined {
91    // logic to find ceiling value in TreeSet
92}
93
94function floorInTreeSet(val: number): number | undefined {
95    // logic to find floor value in TreeSet
96}
97
98// ... Continue with additional global methods for the TreeSet functionality
99
100// Other necessary global methods and variable declarations follow the same convention as shown above.
101
Not Sure What to Study? Take the 2-min Quiz：

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Time and Space Complexity

The given Python code defines a class DinnerPlates with methods to push and pop elements from a set of stacks, with a specific capacity. The code makes use of the SortedSet from the sortedcontainers module to keep track of stacks that are not full.

Time Complexity

  • init(self, capacity: int): O(1) The constructor initializes variables. The creation of an empty list and a SortedSet is done in constant time.

  • push(self, val: int): O(logN)

    • If the not_full SortedSet is empty, appending to the list of stacks is O(1).
    • If there are indices in not_full, inserting at a specific index in a list is O(1), but adding or removing from a SortedSet has O(logN) complexity, due to the underlying tree structure.

  • pop(self): O(logN)

    • This method calls popAtStack with the index of the last stack. The complexity will depend on popAtStack.

  • popAtStack(self, index: int): O(N) or O(logN)

    • Popping from the stack itself is O(1).
    • The complexity varies based on the condition inside the method. If we're popping from the last stack, and we need to remove empty stacks, we could have a case where we remove up to N stacks, hence O(N). However, if we're removing from the SortedSet due to the stack not being full anymore, it will be O(logN).

Assuming N as the number of stacks:

  • For push operations, it's generally O(logN) due to the addition and removal process in the SortedSet which maintains order.
  • For pop operations, provided we do not always pop from an empty stack requiring the removal of multiple stacks, we can consider it O(logN) as well. However, in the worst case where we clean up many empty stacks, it will be O(N).

Space Complexity

  • Overall Space Complexity: O(N * C)
    • N is the maximum number of stacks that have been created, and C is the capacity of each stack.
    • The space complexity takes into account the list self.stacks that stores stacks and each stack can potentially store up to C items.
    • The SortedSet self.not_full contains at most N indices, and therefore its space complexity is O(N).

Therefore, the space complexity of maintaining the structure is determined by both the number of stacks and their capacity.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of these properties could exist for a graph but not a tree?

Recommended Readings

Stack Intro

Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you

Heap Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫