1172. Dinner Plate Stacks

https://leetcode.com/problems/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.
• void push(int val) pushes the given positive integer val into the leftmost stack with 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 stacks are empty.
• int popAtStack(int index) returns the value at the top of the stack with the given index and removes it from that stack, and 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 <= 20000
• 1 <= val <= 20000
• 0 <= index <= 100000
• At most 200000 calls will be made to push, pop, and popAtStack.

---

Intuition

Stacks can get filled, or empty left to right, and number of stacks can increase => track the stacks in a list

Track the first, and last stack which are not empty

push

    find first stack which is not full

    Push plate to that stack

    Update the last stack = max(last, first)

pop

    find last stack which is not empty

    if last == -1 => return -1

    Update the first stack = min(first, last)

    pop from last stack and return

pop at index

    if invalid index or empty stack at index

        return -1

    Update first stack = min(first, index)

    pop from stack at index and return

---

	class DinnerPlates {
	List<Stack<Integer>> list;
	int full;
	int first, last;
	public DinnerPlates(int capacity) {
	list = new ArrayList<Stack<Integer>>();
	full = capacity;
	first = 0;
	last = 0;
	}
	public void push(int val) {
	// detect first stack thats not full
	while (first < list.size() && list.get(first).size() == full) {
	first++;
	}
	// all stacks in the front are full
	if (first == list.size()) {
	list.add(new Stack<Integer>());
	}
	list.get(first).push(val);
	// Save last stack with plates
	last = Math.max(first, last);
	}
	public int pop() {
	// detect last stack thats not empty
	while (last >= 0 && list.get(last).isEmpty()) {
	last--;
	}
	// all stacks are empty
	if (last == -1) {
	return -1;
	}
	// Save first stack with plates
	first = Math.min(first, last);
	return list.get(last).pop();
	}
	public int popAtStack(int index) {
	if (index >= list.size() || list.get(index).isEmpty()) {
	return -1;
	}
	// Save first stack with plates
	first = Math.min(first, index);
	return list.get(index).pop();
	}
	}
	/**
	* Your DinnerPlates object will be instantiated and called as such:
	* DinnerPlates obj = new DinnerPlates(capacity);
	* obj.push(val);
	* int param_2 = obj.pop();
	* int param_3 = obj.popAtStack(index);
	*/

view raw 1172.DinnerPlateStacks.java hosted with ❤ by GitHub