LeetCode 1172: Dinner Plate Stacks Solution
Master LeetCode problem 1172 (Dinner Plate Stacks), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
1172. Dinner Plate Stacks
Problem Explanation
Explanation
This problem can be efficiently solved using a combination of data structures. We can maintain a list of stacks to store the elements and a set to keep track of available stacks. When pushing an element, we find the leftmost available stack and push the element onto it. When popping an element, we find the rightmost non-empty stack and pop the element from it. When popping from a specific stack, we check if it is non-empty and pop the element accordingly.
Algorithm:
- Initialize necessary data structures - a list of stacks, a set of available stacks, and the maximum capacity per stack.
- When pushing an element:
- If there are no available stacks, create a new stack and add it to the list of stacks and available stacks.
- Otherwise, find the leftmost available stack and push the element onto it.
- When popping an element:
- If all stacks are empty, return -1.
- Otherwise, find the rightmost non-empty stack and pop the element from it.
- When popping from a specific stack:
- If the specified stack is empty, return -1.
- Otherwise, pop the element from the specified stack.
Time Complexity:
- Push: O(1) on average
- Pop: O(1) on average
- PopAtStack: O(1)
Space Complexity: O(n), where n is the total number of elements pushed.
Solution Code
class DinnerPlates {
private List<Stack<Integer>> stacks;
private Set<Integer> availableStacks;
private int capacity;
public DinnerPlates(int capacity) {
this.stacks = new ArrayList<>();
this.availableStacks = new TreeSet<>();
this.capacity = capacity;
}
public void push(int val) {
if (availableStacks.isEmpty()) {
stacks.add(new Stack<>());
availableStacks.add(stacks.size() - 1);
}
int stackIndex = availableStacks.iterator().next();
Stack<Integer> stack = stacks.get(stackIndex);
stack.push(val);
if (stack.size() == capacity) {
availableStacks.remove(stackIndex);
}
}
public int pop() {
if (stacks.isEmpty()) {
return -1;
}
int stackIndex = stacks.size() - 1;
while (stackIndex >= 0 && stacks.get(stackIndex).isEmpty()) {
stackIndex--;
}
if (stackIndex < 0) {
return -1;
}
int val = stacks.get(stackIndex).pop();
if (stacks.get(stackIndex).isEmpty()) {
availableStacks.remove(stackIndex);
}
return val;
}
public int popAtStack(int index) {
if (index < 0 || index >= stacks.size() || stacks.get(index).isEmpty()) {
return -1;
}
int val = stacks.get(index).pop();
if (stacks.get(index).isEmpty()) {
availableStacks.remove(index);
}
return val;
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 1172 (Dinner Plate Stacks)?
This page provides optimized solutions for LeetCode problem 1172 (Dinner Plate Stacks) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 1172 (Dinner Plate Stacks)?
The time complexity for LeetCode 1172 (Dinner Plate Stacks) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 1172 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1172 in Java, C++, or Python.