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.
This approach involves using dynamic programming to decide the optimal cutting of shelves using the given books. Let df[i] be the minimum height for placing the first i books. For each book i, you consider ending a new shelf at book i but try every starting point from j = i to find the best cut. The key here is to use a nested loop to calculate the minimum height iteratively.
This solution uses an integer array df of size booksSize + 1, where each element df[i] represents the minimum height of the bookshelf containing the first i books. Two nested loops check each combination to find the minimum. The outer loop selects to end a shelf with the i-th book, while the inner loop determines the start of that shelf.
Time Complexity: O(n^2), where n is the number of books.
Space Complexity: O(n), due to the use of extra space for the dp array.
This strategy uses a recursive backtracking approach augmented with memoization to avoid redundant calculations. By attempting to place books on shelves recursively and caching computed heights, it achieves optimal placement efficiently. This method provides a balance between direct computation and saved results.
The C code recursively tries to place each book on a new shelf or the current shelf. It uses a memoization array dp to store computed minimum heights for the subproblems, avoiding recomputation. This recursion explores every possibility and chooses the arrangement yielding the minimum height incrementally.
Time Complexity: O(n^2), primarily constrained due to state saving over recursion calls
Space Complexity: O(n), requires extra space for memoization.
We define f[i] as the minimum height for placing the first i books, initially f[0] = 0, and the answer is f[n].
Consider f[i], the last book is books[i - 1], its thickness is w, and its height is h.
f[i] = f[i - 1] + h;books[j-1] on the same layer from back to front, where j \in [1, i - 1], accumulate the thickness of the book to w, if w > shelfWidth, it means that books[j-1] can no longer be placed on the same layer with books[i-1], stop enumeration; otherwise, we update the maximum height h = max(h, books[j-1][1]) of the current layer, then f[i] = min(f[i], f[j - 1] + h).The final answer is f[n].
The time complexity is O(n^2), and the space complexity is O(n). Here, n is the length of the array books.
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n^2), where n is the number of books. |
| Backtracking with Memoization | Time Complexity: O(n^2), primarily constrained due to state saving over recursion calls |
| Dynamic Programming | — |
| 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 |
Filling Bookcase Shelves - Leetcode 1105 - Python • NeetCodeIO • 20,313 views views
Watch 9 more video solutions →Practice Filling Bookcase Shelves with our built-in code editor and test cases.
Practice on FleetCode