{x}
blog image

Dinner Plate Stacks

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

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.

Solution Explanation: Dinner Plate Stacks

This problem requires designing a data structure that efficiently manages an arbitrary number of stacks, each with a fixed capacity. The solution uses a combination of a list of stacks (to hold the actual data) and a sorted set (to track stacks that aren't full). This combination allows for efficient push and pop operations from both the leftmost and rightmost stacks.

Data Structures:

  • capacity: An integer representing the maximum capacity of each stack.
  • stacks: A list (or array) of stacks. Each inner stack stores integers. The list's index corresponds to the stack's number.
  • not_full: A sorted set (e.g., TreeSet in Java, SortedSet in Python with the sortedcontainers library, std::set in C++) that stores the indices of stacks that are not yet full. The sorted nature allows for quickly finding the leftmost available stack during a push operation.

Operations:

  • DinnerPlates(capacity): Initializes the capacity, creates an empty stacks list, and initializes an empty not_full sorted set.

  • push(val):

    1. If not_full is empty, all stacks are full. A new stack is created and val is pushed onto it. If the capacity is greater than 1, the index of the new stack is added to not_full.
    2. If not_full is not empty, the smallest index (leftmost non-full stack) from not_full is retrieved. val is pushed onto that stack. If pushing val makes the stack full, its index is removed from not_full.

  • pop():

    1. This operation pops from the rightmost non-empty stack. It essentially calls popAtStack(stacks.size() - 1).

  • popAtStack(index):

    1. It checks if the index is valid and if stacks[index] is non-empty. If either is false, it returns -1.
    2. The top element from stacks[index] is popped and returned.
    3. If the popped element was from the rightmost stack and now that stack is empty, the code iteratively removes empty stacks from the stacks list and their indices from not_full until a non-empty rightmost stack is found or the list is empty.
    4. Otherwise (if the popped element wasn't from the rightmost stack), the index of the stack is added back to not_full because it's no longer full.

Time Complexity Analysis:

  • push(val): O(log n) for not_full operations (insertion/deletion/retrieval of the smallest element), where n is the number of stacks. The rest of the push operation is O(1).
  • pop(): O(log n) in the worst case (if many rightmost stacks are empty). It involves removing empty stacks, which impacts not_full and the stacks list.
  • popAtStack(index): O(log n) in the worst case due to potential removal of trailing empty stacks. The rest of the operation is O(1).

Overall, the amortized time complexity of all operations is O(log n), making it efficient even for a large number of stacks and operations.

Space Complexity:

The space complexity is O(m + k), where m is the maximum number of elements ever stored across all stacks and k is the maximum number of stacks simultaneously in use. stacks can grow up to size k, and not_full has a size at most k.

The provided code in Python, Java, C++, Go, and TypeScript implements this solution, using appropriate data structures for each language. The Go code uses a redblacktree package for efficient sorted set implementation. The TypeScript code includes a custom implementation of a Red-Black Tree and TreeSet for the sorted set functionality. Remember to install the necessary libraries (sortedcontainers for Python) if you use the provided Python solution.