Skip to main content

Stack

Dinner Plate Stacks

Problem Statement

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.

Example

Input
["DinnerPlates", "push", "push", "push", "push", "push", "popAtStack", "push", "push", "popAtStack", "popAtStack", "pop", "pop", "pop", "pop", "pop"]
[[2], [1], [2], [3], [4], [5], [0], [20], [21], [0], [2], [], [], [], [], []]
Output
[null, null, null, null, null, null, 2, null, null, 20, 21, 5, 4, 3, 1, -1]

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.
💡
Try Solving it Yourself First !
This is a design based problem statement, which involves implementing the functionalities, we need to understand the output flow and figure out the algorithm accordingly. Let's take an example as given and perform the operations on paper and analyse how we can efficiently figure out the working algorithm !!

Optimal Approach

Intuition

If we observe, this design question doesn't involve much of logical thinking, rather we must have an idea of various data structures and know how to use them efficiently.

We are given an infinite number of stacks arranged in a line, and each stack has a capacity x.

This means that each of the stacks can hold up to a capacity of 2 according to the above image.

This looks like we use a data structure which is a combination of List/Vector and in each index, a stack of specific size is placed.

We are given a constraint that each stack can hold "capacity" number of plates.
Suppose each of the stack can hold 2 numbers.
Let's say we want to push 1,2,3,4 on this data-structure.

When we wanted to push number 3, first we checked if the first stack was empty or not, if it was not then we will insert another stack on to the list and then added the number to the top of stack.

For this we have to maintain a record on which stack is empty or not

Initially, when we entered the number 1 into the List<Stack<Integer>> data structure. We initialized a stack and entered on it. When we added number 2 on to the data structure, we checked whether the stack at index 0 is empty or not ??

How did we check?? Can we maintain a record that we use to check whether a stack is empty or not?

Probably, we can maintain a record where we note down the index of the List which has free-spaced stack available.

Let's again understand the flow,
We are given a capacity of 2, we want to push 1,2,3,4 on the List<Stack<Integer>>.

First , we will push 1 to the List<Stack<Integer>>

What will happen if, we add 2 to the stack ?

When we, push 3

Similarly, we push 4 to the List<Stack<Integer>>

Now, let's see how we can perform the pop() and popAtStack() functions, the pop() function removes the top-most number of the stack present in the right-most index.

When we call the pop() function , we remove the number 4 which is present at the last index of List<Stack<Integer>> i.e. 1 at remove the top of it.

We did two things,
1. retrieve the last index of List<Stack<Integer>> and remove the topmost number in that stack.
2. Added the index 1 to the record.

Now, suppose we have 1,2,3,4,5 in List<Stack<Integer>>.

We want to perform popAtStack(1),

1. what we do is we retrieve the stack at index 1 and check if the stack is empty or not, if it not, we remove 4 from top of that particular stack.
2. Added 1 to the record.

Now, if we want to insert a number 6 into the data structure, where to insert ??
Since, there are two half filled stacks. We will pick-up the stack which occurred first.

Here, comes that the record we are maintaining must store the values in sorted order and also we can retrieve them in lesser time.

Why the record must store values in Sorted manner ?

If the record stores in sorted manner i.e. in increasing manner, we can retrieve the first value from it which signifies, the stack at that particular index is empty from left.

Which data-structure we must choose that fulfils this demand.
Either we can use a Min-Heap or a ordered_set/TreeSet .

Let's maintain a TreeSet of Integers to store the index of empty stacks.

When we want to push 6,

1. We retrieved the first value from TreeSet
2. We traced that particular index in the List<Stack>.
3. We added 6 to the stack.
4. We checked the capacity is full or not
5. Inserting 6 made the stack full, so we removed index 1 from the set.

Let's See How we Can Code it up !!!

Approach

Initialization

  • Create a list of stacks to hold elements (stacks).
  • Set the stack capacity to the given value (capacity).
  • Create a set to track available stacks with space (availableStack).

Push Operation

  • If there are no available stacks with space: Add a new stack to the list.
    Mark this new stack as available.
  • Get the first available stack (the one with the smallest index) from availableStack.
  • Push the value into this stack.
  • If the stack becomes full after adding the value: Remove its index from availableStack.

Pop Operation

  • If the list of stacks is empty, return -1.
  • Remove and retrieve the top element from the last stack in the list.
  • Mark the last stack as available in availableStack.
  • If the last stack becomes empty: Remove it from the list. Remove its index from availableStack.
  • Return the retrieved element.

PopAtStack Operation

  • If the given index is out of bounds (greater than or equal to the number of stacks), return -1.
  • If the given index is the last stack in the list: Call the pop operation. Return the result.
  • Retrieve the stack at the given index.
  • If the stack is empty, return -1.
  • Remove and retrieve the top element from the stack.
  • Mark this stack as available in availableStack.
  • Return the retrieved element.

Dry-Run

Input
["DinnerPlates", "push", "push", "push", "push", "push", "popAtStack", "push", "push", "popAtStack", "popAtStack", "pop", "pop", "pop", "pop", "pop"]

Arguments:
[[2], [1], [2], [3], [4], [5], [0], [20], [21], [0], [2], [], [], [], [], []]

Output: [null, null, null, null, null, null, 2, null, null, 20, 21, 5, 4, 3, 1, -1]

Dry Run

Initialization: DinnerPlates(2)

  • stacks = [] (no stacks yet)
  • availableStack = {} (no available stacks)

Operation 1: push(1)

availableStack is empty → Add a new stack.
Push 1 into stacks[0].
Resulting State:

  • stacks = [[1]]
  • availableStack = {0}

Operation 2: push(2)
Push 2 into stacks[0].
Stack at index 0 is now full → Remove 0 from availableStack.
Resulting State:

  • stacks = [[1, 2]]
  • availableStack = {}

Operation 3: push(3)
availableStack is empty → Add a new stack.
Push 3 into stacks[1].
Resulting State:

  • stacks = [[1, 2], [3]]
  • availableStack = {1}

Operation 4: push(4)
Push 4 into stacks[1].
Stack at index 1 is now full → Remove 1 from availableStack.
Resulting State:

  • stacks = [[1, 2], [3, 4]]
  • availableStack = {}

Operation 5: push(5)
availableStack is empty → Add a new stack.
Push 5 into stacks[2].
Resulting State:

  • stacks = [[1, 2], [3, 4], [5]]
  • availableStack = {2}

Operation 6: popAtStack(0)
Pop the top of stacks[0] → Value = 2.
Add 0 to availableStack.
Resulting State:

  • stacks = [[1], [3, 4], [5]]
  • availableStack = {0, 2}

Operation 7: push(20)
Push 20 into stacks[0].
Stack at index 0 is now full → Remove 0 from availableStack.
Resulting State:

  • stacks = [[1, 20], [3, 4], [5]]
  • availableStack = {2}

Operation 8: push(21)
Push 21 into stacks[2].
Stack at index 2 is now full → Remove 2 from availableStack.
Resulting State:

  • stacks = [[1, 20], [3, 4], [5, 21]]
  • availableStack = {}

Operation 9: popAtStack(0)
Pop the top of stacks[0] → Value = 20.
Add 0 to availableStack.
Resulting State:

  • stacks = [[1], [3, 4], [5, 21]]
  • availableStack = {0}

Operation 10: popAtStack(2)
Pop the top of stacks[2] → Value = 21.
Add 2 to availableStack.
Resulting State:

  • stacks = [[1], [3, 4], [5]]
  • availableStack = {0, 2}

Operation 11: pop()
Pop the top of the last stack (stacks[2]) → Value = 5.
Remove 2 from availableStack if it becomes empty.
Resulting State:

  • stacks = [[1], [3, 4]]
  • availableStack = {0}

Operation 12: pop()
Pop the top of the last stack (stacks[1]) → Value = 4.
Resulting State:

  • stacks = [[1], [3]]
  • availableStack = {0}

Operation 13: pop()
Pop the top of the last stack (stacks[1]) → Value = 3.
Resulting State:

  • stacks = [[1]]
  • availableStack = {0}

Operation 14: pop()
Pop the top of the last stack (stacks[0]) → Value = 1.
Resulting State:

  • stacks = []
  • availableStack = {}

Operation 15: pop()
No stacks left → Return -1.

Output: [null, null, null, null, null, null, 2, null, null, 20, 21, 5, 4, 3, 1, -1]

Optimal Code in all Languages.
1. C++ Try on Compiler 
class DinnerPlates {
    vector<stack<int>> stacks; // List to store stacks
    int capacity;              // Capacity of each stack
    set<int> availableStack;   // Set to track stacks with space for push

public:
    DinnerPlates(int capacity) {
        // Initialize stacks and capacity
        this->capacity = capacity;
    }

    void push(int val) {
        // If no stack has space, create a new stack
        if (availableStack.empty()) {
            stacks.emplace_back(stack<int>());
            availableStack.insert(stacks.size() - 1);
        }

        // Push the value into the first available stack
        int index = *availableStack.begin();
        stacks[index].push(val);

        // Remove stack from availableStack if it becomes full
        if (stacks[index].size() == capacity) {
            availableStack.erase(index);
        }
    }

    int pop() {
        // If no stacks are present, return -1
        while (!stacks.empty() && stacks.back().empty()) {
            stacks.pop_back();
            availableStack.erase(stacks.size());
        }
        if (stacks.empty()) return -1;

        // Pop value from the last stack
        int val = stacks.back().top();
        stacks.back().pop();
        availableStack.insert(stacks.size() - 1);

        return val;
    }

    int popAtStack(int index) {
        // If index is invalid or stack is empty, return -1
        if (index >= stacks.size() || stacks[index].empty()) return -1;

        // Pop value from the specified stack
        int val = stacks[index].top();
        stacks[index].pop();
        availableStack.insert(index);

        return val;
    }
};

2. Java Try on Compiler 
class DinnerPlates {

    // List to store stacks
    List<Stack<Integer>> stacks;

    // Capacity of each stack
    int capacity;

    // TreeSet to keep track of available stacks for push operation
    TreeSet<Integer> availableStack;

    public DinnerPlates(int capacity) {
        // Initialize the stacks, capacity, and availableStack
        this.stacks = new ArrayList<Stack<Integer>>();
        this.capacity = capacity;
        this.availableStack = new TreeSet<Integer>();
    }

    public void push(int val) {
        // If no stack has space, create a new stack
        if (availableStack.isEmpty()) {
            stacks.add(new Stack<Integer>());
            availableStack.add(stacks.size() - 1);
        }

        // Get the first stack with available space
        Stack<Integer> firstStackWithSpace = stacks.get(availableStack.first());
        // Push the value into the stack
        firstStackWithSpace.push(val);

        // If the stack is now full, remove it from availableStack
        if (firstStackWithSpace.size() == capacity) {
            availableStack.pollFirst();
        }
    }

    public int pop() {
        // If no stacks are present, return -1
        if (stacks.isEmpty()) {
            return -1;
        }

        // Pop the value from the last stack
        int val = stacks.get(stacks.size() - 1).pop();

        // Add the index of the last stack to availableStack
        availableStack.add(stacks.size() - 1);

        // Remove all empty stacks from the end
        while (!stacks.isEmpty() && stacks.get(stacks.size() - 1).isEmpty()) {
            stacks.remove(stacks.size() - 1);
            availableStack.pollLast();
        }

        return val;
    }

    public int popAtStack(int index) {
        // If the index is invalid, return -1
        if (index >= stacks.size()) {
            return -1;
        }

        // If the index is the last stack, use the pop() method
        if (index == stacks.size() - 1) {
            return pop();
        }

        // Get the required stack
        Stack<Integer> requiredStack = stacks.get(index);

        // Pop the value if the stack is not empty, otherwise return -1
        int val = requiredStack.isEmpty() ? -1 : requiredStack.pop();

        // Add the index to availableStack
        availableStack.add(index);

        return val;
    }
}

3. Python Try on Compiler 
class DinnerPlates:
    def __init__(self, capacity):
        # Initialize stacks, capacity, and available stack indices
        self.stacks = []
        self.capacity = capacity
        self.available_stack = set()

    def push(self, val):
        # If no stack has space, create a new stack
        if not self.available_stack:
            self.stacks.append([])
            self.available_stack.add(len(self.stacks) - 1)

        # Push value into the first available stack
        index = min(self.available_stack)
        self.stacks[index].append(val)

        # Remove index from available_stack if the stack becomes full
        if len(self.stacks[index]) == self.capacity:
            self.available_stack.remove(index)

    def pop(self):
        # Remove empty stacks from the end
        while self.stacks and not self.stacks[-1]:
            self.stacks.pop()

        # If no stacks are left, return -1
        if not self.stacks:
            return -1

        # Pop value from the last stack
        val = self.stacks[-1].pop()
        self.available_stack.add(len(self.stacks) - 1)
        return val

    def popAtStack(self, index):
        # If index is invalid or stack is empty, return -1
        if index >= len(self.stacks) or not self.stacks[index]:
            return -1

        # Pop value from the specified stack
        val = self.stacks[index].pop()
        self.available_stack.add(index)
        return val

4. JavaScript Try on Compiler 
var DinnerPlates = function(capacity) {
    this.stacks = [];
    this.capacity = capacity;
    this.availableStack = new Set();
};
DinnerPlates.prototype.push = function(val) {
    // If no stack has space, create a new stack
    if (this.availableStack.size === 0) {
        this.stacks.push([]);
        this.availableStack.add(this.stacks.length - 1);
    }

    // Push value into the first available stack
    const index = Math.min(...this.availableStack);
    this.stacks[index].push(val);

    // Remove index from availableStack if the stack becomes full
    if (this.stacks[index].length === this.capacity) {
        this.availableStack.delete(index);
    }
};

DinnerPlates.prototype.pop = function() {
    // Remove empty stacks from the end
    while (this.stacks.length > 0 && this.stacks[this.stacks.length - 1].length === 0) {
        this.stacks.pop();
    }

    // If no stacks are left, return -1
    if (this.stacks.length === 0) return -1;

    // Pop value from the last stack
    const val = this.stacks[this.stacks.length - 1].pop();
    this.availableStack.add(this.stacks.length - 1);
    return val;
};

DinnerPlates.prototype.popAtStack = function(index) {
    // If index is invalid or stack is empty, return -1
    if (index >= this.stacks.length || this.stacks[index].length === 0) return -1;

    // Pop value from the specified stack
    const val = this.stacks[index].pop();
    this.availableStack.add(index);
    return val;
};

Time Complexity: O(1)

Push Operation:

  • Finding the first available stack: O(logk), where k is the number of available stacks with free space.
  • Pushing the value: O(1).
  • Total: O(logk).

Pop Operation:

  • Removing empty stacks from the end: O(m−s), where m is the total number of stacks, and s is the number of non-empty stacks.
  • Popping a value: O(1).
  • Updating available indices: O(log⁡m).
  • Total: O(m−s+log⁡m).

PopAtStack Operation:

  • Accessing the specified stack and popping: O(1).
  • Updating available indices: O(log⁡m).
  • Total: O(logm).

There can be 2 * 105 calls made at max to push(), pop() and popAtStack(). So the Total Time Complexity is: O(1) + O(1) + O(1) = O(1) * 2 * 10^5 = O(1).

Space Complexity: O(1)

Auxiliary Space Complexity:
Auxiliary space refers to the extra space required by an algorithm other than the input space.
Minimal space is used for index tracking: O(1) per operation.

Total Space Complexity:
O(n + m), where n is the total number of elements, and m is the total number of stacks.
n for storing all elements and m for managing the stacks and indices.

At max 2 * 10^5 calls can be made to the push() which will occupy a space of O(2* 10^5) = O(1).

Learning Tip

Maximum Frequency Stack

Design a stack-like data structure to push elements to the stack and pop the most frequent element from the stack.

Implement the FreqStack class:

FreqStack() constructs an empty frequency stack.

void push(int val) pushes an integer val onto the top of the stack.

int pop() removes and returns the most frequent element in the stack.
If there is a tie for the most frequent element, the element closest to the stack's top is removed and returned.

💡
Showcase your skills by joining LearnYard Technologies FZ-LLC as a Technical Content Writer. Apply now and inspire the next generation of learners—fill out the form: https://forms.gle/CGDsbGkcapSfvXKM8