PROBLEM LINKS
DIFFICULTY
EASY
PREREQUISITES
Stack Data Structure
PROBLEM
Harry has a lot of books messed on the floor. He keeps a pile of books. At any time, he can put a book that has some remaining exercises on top of the pile, or do a book exercise by picking a book with minimum number of remaining exercises and removing all books above it. If there are more than one such book, pick the book with the minimum number of removed books. Help him determine which book to pick whenever he wants to do a book exercise.
QUICK EXPLANATION
Maintain a stack of books. Each book is represented by a pair of (name, number of remaining exercises, number of books above with greater number of remaining exercises). When Harry wants to do a book exercise, pop the stack and retrieve the name of the book. When Harry wants to put a book on the top of the stack, there are two possibilities. If the number of remaining exercises is greater than the number of remaining exercises of the book on the top of the stack, ignore this book and increase the “number of books above” of the book on the top of the stack. Otherwise, push a new book (name of the book, number of remaining exercises, 0) to the stack.
The time complexity of this solution is of course linear.
EXPLANATION
This is clearly a data structure problem. The problem statement implies that we need to invent an augmented (modified) stack that supports these operations.
- Add a book on the top of the stack.
- Retrieve a book with the minimum number remaining exercises, and pop all books above it, including the book itself.
To solve this problem, we need this important lemma.
Lemma 1. Suppose there is a book A above a book B in the pile, and book A has greater number of remaining exercises than B. Then, book A will never get picked by Harry.
Proof. Because Harry always pick a book with the minimum number of remaining exercises, book B must be removed first before book A can be picked. However, removing book B will remove book A as well. Therefore, book A will never get picked.
Lemma 1 implies that we don’t have to physically put a book above another book with lower number of remaining exercises as the book can’t be picked. For each book, we can just store the number of books above it that have greater number of remaining exercises. Therefore, we have a stack in non-decreasing order of number of remaining exercises from top to bottom. All operations above can then be implemented in constant time:
- If the number of remaining exercises is greater than the number of remaining exercises of the book on the top of the stack, ignore this book (as this book can be never get picked) and increase the "number of books above" of the book on the top of the stack. Otherwise, push a new book (name of the book, number of remaining exercises, 0) to the stack. Of course, if the stack is initially empty, we can just push the book to the stack.
- As the stack is sorted in non-decreasing order, just retrieve the book on the top of the stack (and pop it).
Because each operation is done in constant time, the whole solution runs in O(N), i.e., linear time.
Note. There is a tricky case in this problem! When Harry grabs a book with no remaining exercises, he does not put in to the pile.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.