Bookshelf Shift

Medium

Online Assessment

Shelve and remove books on a library's numbered shelves, where a new book nudges its neighbours to the right and the last book may spill onto the next shelf.

The library has several shelves in a row. Each shelf is a fixed number of slots, and each slot holds either one book (identified by its positive integer call number) or nothing (0). Reading all slots shelf by shelf, left to right, the books are in strictly increasing call-number order, with empty slots anywhere in between. Call numbers are unique.

Process the commands in order:

["take", b]: if book b is on a shelf, its slot becomes empty and nothing else moves. Otherwise nothing happens.
["add", b]: if book b is already on a shelf, nothing happens. Otherwise the book belongs just after the last book with a smaller call number, in reading order, which means: the target slot is the slot immediately after that book's slot, or slot 0 of the next shelf if that book is in the last slot of its shelf. If there is no smaller book, the target is slot 0 of the first shelf. If the target would be past the end of the last shelf, b goes straight onto the cart (see below). Otherwise:
if the target slot is empty, put b there;
if it is occupied, the unbroken run of occupied slots starting at the target slot moves one slot to the right, to make room, and b takes the target slot. If that run reaches the end of the shelf with no empty slot, the shelf's last book does not fit: it is pushed onto the next shelf as if it were being added at slot 0 of that shelf (so it makes the same kind of room there, and may in turn push that shelf's last book further on). A book pushed off the last shelf goes to the cart.

The cart is a list that collects, in order, every book that ends up with nowhere to go. Books on the cart are not on a shelf, so take ignores them and add may shelve one again.

Input: shelves, a list of shelves, each a list of slot values (0 for empty); commands, a list of ["add", b] and ["take", b].

Output: a list [shelves, cart]: the final shelves (same shape as the input) and the cart.

Example 1

Input:: [[[2,0,5,0],[9,10,0,0]],[["add",7],["add",3],["add",6],["add",8],["add",11],["add",1],["take",5],["add",5],["add",5],["take",99]]]
Output:: [[[1,2,3,5],[6,7,8,9]],[11,10]]
Explanation: Shelves [2,0,5,0] [9,10,0,0]. add 7: the last smaller book is 5 (slot 2), so 7 goes to slot 3 (empty). add 3 goes to slot 1 (after 2). add 6: the target is slot 3, occupied by 7, and the run reaches the end of the shelf, so 7 is pushed to slot 0 of shelf 2, where 9 and 10 shift right (shelf 2 is [7,9,10,0]) and 6 takes the slot. add 8 shifts 9 and 10 into the empty slot. add 11 has its target past the last shelf, so it goes to the cart. add 1 has no smaller book: target is slot 0 of shelf 1, the run 2,3,5,6 pushes 6 to shelf 2, which pushes 10 to the cart. take 5 empties a slot without moving anything, add 5 puts it back (the target is slot 3, after 3), and the second add 5 and take 99 do nothing.

Example 2

Input:: [[[4,5,0],[0,12,15],[20,0,0]],[["add",6],["add",13],["add",5],["add",16],["add",10],["take",12],["add",11],["add",30]]]
Output:: [[[4,5,6],[10,11,13],[15,16,20]],[30]]
Explanation: Shelves [4,5,0] [0,12,15] [20,0,0]. add 6 goes after 5 into the empty slot. add 13 targets the slot after 12, which holds 15; the run ends at the shelf end, so 15 is pushed to slot 0 of shelf 3 where 20 shifts one slot right. add 5 is already on a shelf. add 16 goes after 15 and shifts 20 right. add 10: the last smaller book is 6, in the last slot of shelf 1, so the target is slot 0 of shelf 2, which is empty. After take 12, add 11 goes after 10 into the freed slot (the 13 does not move). add 30 follows 20, which is in the very last slot, so it goes to the cart.

Example 3

Input:: [[[3,4],[8,9]],[["add",9],["add",20],["take",8],["add",21],["add",10],["add",1],["take",21],["add",21]]]
Output:: [[[1,3],[4,9]],[20,21,10,21]]
Explanation: Shelves [3,4] [8,9]. add 9 is already shelved. add 20 and the later add 21 and add 10 have the target past the end of the last shelf, because their last smaller book (9) is in the last slot, so all three go to the cart, in that order. take 8 leaves a gap. add 1 has no smaller book: target is slot 0, and the run 3,4 fills the shelf, so 4 is pushed to slot 0 of the second shelf (which is empty) and shelf 1 is [1,3]. take 21 ignores the book on the cart, so add 21 puts it on the cart a second time.

Constraints

1 ≤ shelves.length ≤ 5; each shelf has between 1 and 8 slots
slot values and call numbers are integers from 1 to 99, with 0 meaning empty; the initial shelves follow the ordering described
0 ≤ commands.length ≤ 60