Filling Bookcase Shelves
MedPrompt
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.
- For example, if we have an ordered list of
5books, 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 <= 1000
Approaches
2 approaches with complexity analysis and trade-offs.
This approach uses a straightforward recursive method to explore every possible valid arrangement of books on the shelves. It starts from the first book and, for each book, tries all possibilities of forming a shelf with the subsequent books. This exhaustive search guarantees finding the minimum height but at a very high computational cost.
Algorithm
- Define a recursive function
solve(i)that computes the minimum height for placing books from indexito the end. - Base Case: If
iequals the total number of booksn, it means all books are placed, so return 0. - Recursive Step: For the current book
i, we try to form a new shelf by including books fromitoj(wherejranges fromiton-1).- Initialize
min_heightto infinity. - Start a loop for
jfromiton-1. - In the loop, maintain the
current_shelf_widthandcurrent_shelf_heightfor books fromitoj. - If
current_shelf_widthexceedsshelfWidth, break the loop as no more books can be added to this shelf. - Otherwise, calculate the total height for this configuration:
current_shelf_height + solve(j + 1). - Update
min_height = min(min_height, current_shelf_height + solve(j + 1)).
- Initialize
- Return
min_height. - The initial call is
solve(0).
Walkthrough
We define a recursive function, say solve(i), which calculates the minimum height required to place books from index i to the end of the array. The base case for the recursion is when i reaches the end of the books array, at which point we return 0 as no more books need to be placed.
In the recursive step, for the current book at index i, we iterate through the subsequent books (from i to n-1) to form a new shelf. For each potential shelf containing books from i to j, we first check if its total thickness is within the shelfWidth. If it is, we calculate the height of this shelf (which is the maximum height of any book on it) and add it to the result of the recursive call for the remaining books, i.e., solve(j + 1). We keep track of the minimum total height found among all valid choices for the current shelf.
This method repeatedly solves the same subproblems. For example, solve(5) will be called from solve(0), solve(1), solve(2), etc., leading to an exponential number of function calls.
class Solution { public int minHeightShelves(int[][] books, int shelfWidth) { return solve(books, shelfWidth, 0); } private int solve(int[][] books, int shelfWidth, int i) { if (i == books.length) { return 0; } int minTotalHeight = Integer.MAX_VALUE; int currentShelfWidth = 0; int currentShelfHeight = 0; // Try placing books from i to j on the current shelf for (int j = i; j < books.length; j++) { int thickness = books[j][0]; int height = books[j][1]; currentShelfWidth += thickness; if (currentShelfWidth > shelfWidth) { break; } currentShelfHeight = Math.max(currentShelfHeight, height); int remainingHeight = solve(books, shelfWidth, j + 1); // We need to handle the case where remainingHeight is MAX_VALUE to avoid overflow if (remainingHeight != Integer.MAX_VALUE) { minTotalHeight = Math.min(minTotalHeight, currentShelfHeight + remainingHeight); } } return minTotalHeight; }}Complexity
Time
O(2^n), where n is the number of books. The number of ways to partition the books into shelves can be exponential, leading to an exponential number of recursive calls.
Space
O(n), where n is the number of books. This is due to the maximum depth of the recursion stack.
Trade-offs
Pros
Simple to understand and implement as it directly models the problem's decision-making process.
Correctly solves the problem for very small inputs.
Cons
Extremely inefficient due to a large number of redundant calculations for the same subproblems.
Will result in a 'Time Limit Exceeded' error on most platforms for the given constraints.
This problem exhibits optimal substructure and overlapping subproblems, making it ideal for dynamic programming. We can build a solution iteratively (bottom-up) by calculating the minimum height for an increasing number of books. We use a DP array, dp[i], to store the minimum height of the bookcase after placing the first i books. This avoids the redundant computations of the brute-force approach.
Algorithm
- Let
nbe the number of books. - Create a DP array
dpof sizen + 1.dp[i]will store the minimum height for the firstibooks. - Initialize
dp[0] = 0(0 books need 0 height) and all otherdp[i]to a large value (infinity). - Iterate
ifrom 1 ton:- This loop computes
dp[i]. - Initialize
current_shelf_width = 0andcurrent_shelf_height = 0. - Iterate
jbackwards fromidown to 1:- The inner loop considers placing books from
j-1toi-1on the last shelf. - Add the thickness of book
j-1tocurrent_shelf_width. - If
current_shelf_widthexceedsshelfWidth, break the inner loop. - Update
current_shelf_height = max(current_shelf_height, height of book j-1). - The total height for this arrangement is
dp[j-1](min height for books before this shelf) +current_shelf_height. - Update
dp[i] = min(dp[i], dp[j-1] + current_shelf_height).
- The inner loop considers placing books from
- This loop computes
- The final answer is
dp[n].
Walkthrough
We define a DP array, dp, of size n+1, where n is the number of books. dp[i] will store the minimum possible height of the bookcase containing the first i books (from index 0 to i-1).
The base case is dp[0] = 0, as a bookcase with zero books has zero height. We then iterate from i = 1 to n to compute each dp[i].
To calculate dp[i], we consider all possibilities for the last shelf. The last shelf must contain book i-1. It might also contain books i-2, i-3, and so on. We can iterate backwards from book i-1 (let's say its index is j-1) and try to add it to the current last shelf. For each group of books [j-1, ..., i-1] that fits on a single shelf, we calculate the height of that shelf (which is the max height in that group) and add it to the minimum height of the bookcase containing books up to j-2, which is already stored in dp[j-1]. We take the minimum over all such valid groupings.
The transition formula is: dp[i] = min(dp[j-1] + max_height_of_shelf(j-1, i-1)) for all j from i down to 1, such that the books from j-1 to i-1 fit on one shelf.
This approach can also be implemented using top-down recursion with memoization, which is conceptually equivalent and yields the same complexity.
class Solution { public int minHeightShelves(int[][] books, int shelfWidth) { int n = books.length; // dp[i] will store the minimum height for the first i books. int[] dp = new int[n + 1]; // Base case: 0 books require 0 height. dp[0] = 0; // Initialize other dp values to a large number. for (int i = 1; i <= n; i++) { dp[i] = Integer.MAX_VALUE; } // Iterate through each book to compute dp values. for (int i = 1; i <= n; i++) { int currentShelfWidth = 0; int currentShelfHeight = 0; // Iterate backwards to consider placing books on the last shelf. // j is the 1-based index of the book. for (int j = i; j > 0; j--) { int thickness = books[j - 1][0]; int height = books[j - 1][1]; currentShelfWidth += thickness; // If the shelf width is exceeded, we can't add more books from before. if (currentShelfWidth > shelfWidth) { break; } // Update the height of the current shelf. currentShelfHeight = Math.max(currentShelfHeight, height); // Update dp[i] with the minimum height. // dp[j-1] is the min height for books before the current shelf. dp[i] = Math.min(dp[i], dp[j - 1] + currentShelfHeight); } } return dp[n]; }}Complexity
Time
O(n^2), where n is the number of books. We have a nested loop structure. The outer loop runs `n` times (for `i` from 1 to `n`), and the inner loop also runs up to `n` times (for `j` from `i` down to 1).
Space
O(n), where n is the number of books. We use a DP array of size `n+1` to store the intermediate results.
Trade-offs
Pros
Efficient and guarantees finding the optimal solution.
Handles the given constraints (n <= 1000) effectively.
Avoids re-computation by storing intermediate results.
Cons
Requires O(n) extra space for the DP table.
The O(n^2) time complexity might be too slow for extremely large inputs, but it's efficient enough for the given constraints.
Solutions
Solution
public class Solution { public int MinHeightShelves(int[][] books, int shelfWidth) { int n = books.Length; int[] f = new int[n + 1]; for (int i = 1; i <= n; ++i) { int w = books[i - 1][0], h = books[i - 1][1]; f[i] = f[i - 1] + h; for (int j = i - 1; j > 0; --j) { w += books[j - 1][0]; if (w > shelfWidth) { break; } h = Math.Max(h, books[j - 1][1]); f[i] = Math.Min(f[i], f[j - 1] + h); } } return f[n]; }}class Solution { public int minHeightShelves ( int [][] books , int shelfWidth ) { int n = books . length ; int [] f = new int [ n + 1 ]; for ( int i = 1 ; i <= n ; ++ i ) { int w = books [ i - 1 ][ 0 ], h = books [ i - 1 ][ 1 ]; f [ i ] = f [ i - 1 ] + h ; for ( int j = i - 1 ; j > 0 ; -- j ) { w += books [ j - 1 ][ 0 ]; if ( w > shelfWidth ) { break ; } h = Math . max ( h , books [ j - 1 ][ 1 ]); f [ i ] = Math . min ( f [ i ], f [ j - 1 ] + h ); } } return f [ n ]; } }class Solution { public: int minHeightShelves ( vector < vector < int >>& books , int shelfWidth ) { int n = books . size (); int f [ n + 1 ]; f [ 0 ] = 0 ; for ( int i = 1 ; i <= n ; ++ i ) { int w = books [ i - 1 ][ 0 ], h = books [ i - 1 ][ 1 ]; f [ i ] = f [ i - 1 ] + h ; for ( int j = i - 1 ; j > 0 ; -- j ) { w += books [ j - 1 ][ 0 ]; if ( w > shelfWidth ) { break ; } h = max ( h , books [ j - 1 ][ 1 ]); f [ i ] = min ( f [ i ], f [ j - 1 ] + h ); } } return f [ n ]; } };class Solution : def minHeightShelves ( self , books : List [ List [ int ]], shelfWidth : int ) -> int : n = len ( books ) f = [ 0 ] * ( n + 1 ) for i , ( w , h ) in enumerate ( books , 1 ): f [ i ] = f [ i - 1 ] + h for j in range ( i - 1 , 0 , - 1 ): w += books [ j - 1 ][ 0 ] if w > shelfWidth : break h = max ( h , books [ j - 1 ][ 1 ]) f [ i ] = min ( f [ i ], f [ j - 1 ] + h ) return f [ n ]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.