Watch 10 video solutions for Filling Bookcase Shelves, a medium level problem involving Array, Dynamic Programming. This walkthrough by NeetCodeIO has 20,313 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an array books where books[i] = [thicknessi, heighti] indicates the thickness and height of the ith book. You are also given an integer shelfWidth.
We want to place these books in order onto bookcase shelves that have a total width shelfWidth.
We choose some of the books to place on this shelf such that the sum of their thickness is less than or equal to shelfWidth, then build another level of the shelf of the bookcase so that the total height of the bookcase has increased by the maximum height of the books we just put down. We repeat this process until there are no more books to place.
Note that at each step of the above process, the order of the books we place is the same order as the given sequence of books.
5 books, we might place the first and second book onto the first shelf, the third book on the second shelf, and the fourth and fifth book on the last shelf.Return the minimum possible height that the total bookshelf can be after placing shelves in this manner.
Example 1:
Input: books = [[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]], shelfWidth = 4 Output: 6 Explanation: The sum of the heights of the 3 shelves is 1 + 3 + 2 = 6. Notice that book number 2 does not have to be on the first shelf.
Example 2:
Input: books = [[1,3],[2,4],[3,2]], shelfWidth = 6 Output: 4
Constraints:
1 <= books.length <= 10001 <= thicknessi <= shelfWidth <= 10001 <= heighti <= 1000Problem Overview: You are given books in a fixed order, where each book has a width and height. Place them on shelves with a maximum shelf width so that the total height of the bookcase is minimized. Books must stay in order, and each shelf’s height equals the tallest book placed on it.
Approach 1: Backtracking with Memoization (Top‑Down DP) (Time: O(n²), Space: O(n))
This approach models the problem as a decision at every book index: either continue placing books on the current shelf or start a new shelf. From index i, iterate forward while the cumulative width stays within shelfWidth. Track the maximum height of the current shelf and recursively compute the minimum height for the remaining books. Memoization stores results for each starting index so the same state is not recomputed repeatedly.
The key insight is that each recursive call represents the minimum height achievable from a specific book index onward. Without memoization the recursion becomes exponential, but caching reduces it to quadratic because each index explores at most n forward placements. This approach is intuitive when you first recognize the problem as overlapping subproblems, a classic pattern in dynamic programming.
Approach 2: Dynamic Programming (Bottom‑Up) (Time: O(n²), Space: O(n))
The bottom‑up dynamic programming version builds the solution iteratively. Define dp[i] as the minimum total height required to place the first i books. For each position i, try placing book i on the current shelf together with previous books. Iterate backward from i while accumulating shelf width and tracking the maximum height of books on that shelf.
For each valid grouping, update dp[i] using dp[j-1] + currentShelfHeight. This effectively decides where the previous shelf ended. The algorithm checks every contiguous group of books that can fit within the width limit, making the complexity quadratic. The data is stored in an array, and the recurrence structure follows standard optimization patterns in dynamic programming.
This approach is typically preferred in production or interviews because it avoids recursion overhead and expresses the state transition clearly. Each state depends only on earlier states, making the logic deterministic and easy to debug.
Recommended for interviews: The bottom‑up dynamic programming solution is what most interviewers expect. It demonstrates that you can convert a recursive idea into an efficient iterative DP. Explaining the top‑down memoized version first can still help show how you derived the recurrence, but implementing the iterative DP shows stronger problem‑solving maturity.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with Memoization (Top‑Down DP) | O(n²) | O(n) | Good for understanding the recurrence and modeling the decision process recursively |
| Dynamic Programming (Bottom‑Up) | O(n²) | O(n) | Preferred in interviews and production due to predictable iteration and no recursion overhead |