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 valueval
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:
-
__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 aSortedSet
, which is part of thesortedcontainers
module. This set will keep track of the indices of stacks that aren't full. -
push(self, val: int)
: This method handles adding a new element to the stacks. Ifself.not_full
is empty, it means there are no partially filled stacks, and we need to create a new stack (list
). We append[val]
toself.stacks
. If there is room for more elements (capacity
greater than 1), the index of the new stack is added toself.not_full
. Ifself.not_full
is not empty, we fetch the index of the leftmost non-full stack (self.not_full[0]
), pushval
to that stack, and check if it becomes full. If it does, the index is removed fromself.not_full
. -
pop(self)
: Popping from the rightmost non-empty stack is equivalent to popping at the index of the last stack inself.stacks
, so this method simply callspopAtStack
withlen(self.stacks) - 1
. -
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 ofself.stacks
and updatesself.not_full
. If the popped stack isn't completely empty, it adds the index toself.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 EvaluatorExample 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.
-
Initialize the
DinnerPlates
object:dinner_plates = DinnerPlates(2)
self.stacks = []
self.not_full = SortedSet()
-
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]]
. Theself.not_full
set is updated to{1}
, indicating that the second stack has space left. -
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]]
. Theself.not_full
set should remain empty because no non-full stacks are available. -
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, soself.not_full
is now{0}
. -
Push another element:
dinner_plates.push(4)
Since there's a non-full stack available (stack 0),
self.stacks
becomes[[1, 4]]
andself.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()!;