In this guide, you will get 1172. Dinner Plate Stacks LeetCode Solution with the best time and space complexity. The solution to Dinner Plate Stacks problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
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 * 104
1 <= val <= 2 * 104
0 <= index <= 105
At most 2 * 105 calls will be made to push, pop, and popAtStack.
Complexity Analysis
Time Complexity: O(\log n)
Space Complexity: O(|\texttt{push()}|)
1172. Dinner Plate Stacks LeetCode Solution in C++
class DinnerPlates {
public:
DinnerPlates(int capacity) : capacity(capacity) {
minHeap.push(0);
}
void push(int val) {
const int index = minHeap.top();
// Add a new stack on demand.
if (index == stacks.size())
stacks.push_back({});
// Push the new value.
stacks[index].push(val);
// If the stack pushed is full, remove its candidacy from `minHeap`.
if (stacks[index].size() == capacity) {
minHeap.pop();
// If `minHeap` is empty, the next available stack index is |stacks|.
if (minHeap.empty())
minHeap.push(stacks.size());
}
}
int pop() {
// Remove empty stacks from the back.
while (!stacks.empty() && stacks.back().empty())
stacks.pop_back();
if (stacks.empty())
return -1;
return popAtStack(stacks.size() - 1);
}
int popAtStack(int index) {
if (index >= stacks.size() || stacks[index].empty())
return -1;
// If the stack is going to have space, add its candiday to `minHeap`.
if (stacks[index].size() == capacity)
minHeap.push(index);
const int val = stacks[index].top();
stacks[index].pop();
return val;
}
private:
const int capacity;
vector<stack<int>> stacks;
// the minimum indices of the stacks to push
priority_queue<int, vector<int>, greater<>> minHeap;
}; /* code provided by PROGIEZ */
1172. Dinner Plate Stacks LeetCode Solution in Java
class DinnerPlates {
public DinnerPlates(int capacity) {
this.capacity = capacity;
minHeap.offer(0);
}
public void push(int val) {
final int index = minHeap.peek();
// Add a new stack on demand.
if (index == stacks.size())
stacks.add(new ArrayDeque<>());
// Push the new value.
stacks.get(index).push(val);
// If the stack pushed is full, remove its candidacy from `minHeap`.
if (stacks.get(index).size() == capacity) {
minHeap.poll();
// If `minHeap` is empty, the next available stack index is |stacks|.
if (minHeap.isEmpty())
minHeap.offer(stacks.size());
}
}
public int pop() {
// Remove empty stacks from the back.
while (!stacks.isEmpty() && stacks.get(stacks.size() - 1).isEmpty())
stacks.remove(stacks.size() - 1);
if (stacks.isEmpty())
return -1;
return popAtStack(stacks.size() - 1);
}
public int popAtStack(int index) {
if (index >= stacks.size() || stacks.get(index).isEmpty())
return -1;
// If the stack is going to have space, add its candiday to `minHeap`.
if (stacks.get(index).size() == capacity)
minHeap.offer(index);
return stacks.get(index).pop();
}
private final int capacity;
private List<Deque<Integer>> stacks = new ArrayList<>();
private Queue<Integer> minHeap = new PriorityQueue<>();
} // code provided by PROGIEZ
1172. Dinner Plate Stacks LeetCode Solution in Python
class DinnerPlates:
def __init__(self, capacity: int):
self.capacity = capacity
self.stacks = []
self.minHeap = [0] # the minimum indices of the stacks to push
def push(self, val: int) -> None:
index = self.minHeap[0]
# Add a new stack on demand.
if index == len(self.stacks):
self.stacks.append([])
# Push the new value.
self.stacks[index].append(val)
# If the stack pushed is full, remove its candidacy from `minHeap`.
if len(self.stacks[index]) == self.capacity:
heapq.heappop(self.minHeap)
# If `minHeap` is empty, the next available stack index is |stacks|.
if not self.minHeap:
heapq.heappush(self.minHeap, len(self.stacks))
def pop(self) -> int:
# Remove empty stacks from the back.
while self.stacks and not self.stacks[-1]:
self.stacks.pop()
if not self.stacks:
return -1
return self.popAtStack(len(self.stacks) - 1)
def popAtStack(self, index: int) -> int:
if index >= len(self.stacks) or not self.stacks[index]:
return -1
# If the stack is going to have space, add its candiday to `minHeap`.
if len(self.stacks[index]) == self.capacity:
heapq.heappush(self.minHeap, index)
return self.stacks[index].pop() # code by PROGIEZ
