All problems

Two-Ended Shelf

Medium · design

A bookshelf holds at most capacity different books in a single row. Every book has an id. The shelf starts empty and receives a list of operations. operations[i] is one of "left", "right", "take", "leftmost" or "rightmost", and ids[i] is the book id for the first three (it is 0 and should be ignored for the other two).

• "left" puts book ids[i] at the far left end of the row. If the book is already on the shelf it is moved there. If the shelf now holds more than capacity books, the book at the far right end is removed.
• "right" puts book ids[i] at the far right end of the row, moving it if it is already on the shelf. If the shelf now holds more than capacity books, the book at the far left end is removed.
• "take" removes book ids[i] from the shelf if it is there, and does nothing otherwise.
• "leftmost" and "rightmost" read the book at that end of the row without removing it.

Return a list with one answer per operation, in order:

• for "left" and "right", the id of the book that was removed to make room, or -1 if none was removed;
• for "take", 1 if the book was on the shelf and has been removed, or 0 if it was not there;
• for "leftmost" and "rightmost", the id of the book at that end, or -1 if the shelf is empty.

Examples

Example 1

Input: capacity = 2, operations = ["left", "left", "right", "leftmost", "rightmost", "take", "rightmost"], ids = [1, 2, 3, 0, 0, 2, 0]

Output: [-1, -1, 2, 1, 3, 0, 3]

After the two lefts the row is 2, 1. Putting 3 on the right makes three books, so the far left book 2 is removed and the row is 1, 3. Book 2 is no longer there to take.

Example 2

Input: capacity = 1, operations = ["left", "left", "take", "leftmost"], ids = [5, 6, 6, 0]

Output: [-1, 5, 1, -1]

Placing 6 on the left pushes 5 off the right end. Taking 6 empties the shelf.

Example 3

Input: capacity = 3, operations = ["left", "left", "left", "right", "left", "rightmost"], ids = [1, 2, 3, 1, 1, 0]

Output: [-1, -1, -1, -1, -1, 2]

Moving a book that is already on the shelf never removes anything, even when the shelf is full.

Constraints

• 1 <= capacity <= 5000
• 1 <= len(operations) <= 10^4
• len(ids) == len(operations)
• operations[i] is one of left, right, take, leftmost, rightmost
• 0 <= ids[i] <= 10^9