Leetcode 1105. Filling Bookcase Shelves
Problem Explanation
We're given a sequence of n
books, each with a specified thickness and height. The task is to shelve these books onto a bookcase of a particular width, such that the total height of the bookcase is minimized. This is subject to the condition that the books must be placed on shelves in the same order they're given, and a shelf can hold as many books as can fit (i.e., the sum of thicknesses is less than or equal to the shelf's width).
Example Walkthrough
Consider the example books = [[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]]
and shelf_width = 4
.
We could first place the book of dimensions [1,1]
onto the first shelf. Then place the next two books [2,3],[2,3]
onto the second shelf (as their total thickness 4
is not greater than shelf_width
). Repeat the process placing the next three books [1,1],[1,1],[1,1]
onto the third shelf and the last book [1,2]
onto the fourth.
After adding up the maximum height of each shelf, the total height of the bookcase is 1+3+1+2=7
.
However, if we rearrange the books a bit, placing the first two books [1,1],[2,3]
onto the first shelf, the next three books [2,3],[1,1],[1,1]
onto the second, and the last two books [1,1],[1,2]
onto the third, we get a total height of 1+3+2=6
. This solution is optimal hence would be our output.
Solution Approach
The solution starts by initializing a dynamic programming (dp) array dp
with a size of n+1
(n being the total number of books) and filled with a large value (INT_MAX
). dp[i]
aims at storing the minimum total height to place the first i
books. The base case dp[0]
is set as 0
since no height is needed when placing zero books.
Next, we iterate over the books. For each book i
, we try to see if placing books i
to j
(i >= j >= 0
) onto a new shelf results in an optimal solution. The sum of thicknesses of these books is cumulated in sumThickness
and the greatest height is tracked in maxHeight
. We break the loop when sumThickness > shelfWidth
as placing the current book leads to an oversized shelf. The optimal height after placing the i-th
book is updated as min(dp[i+1], dp[j] + maxHeight)
. This line translates to comparing the result of two operations:
- placing the book
i
onto a new shelf: the height increases by the maximum height of books located betweenj
andi
. - not shelving the book
i
: the total height remains the same (i.e.,dp[i+1]
).
The process is repeated until all books are examined. The final value in dp
(dp.back()
in C++) holds the least height to place all books in order.
Python Solution
1 2python 3class Solution: 4 def minHeightShelves(self, books, shelf_width): 5 dp = [0] + [float('inf')] * len(books) 6 for i in range(len(books)): 7 width, j = 0, i 8 tallest = 0 9 while j >= 0 and width + books[j][0] <= shelf_width: 10 height, thickness = books[j] 11 width += thickness 12 tallest = max(tallest, height) 13 dp[i+1] = min(dp[i+1], dp[j] + tallest) 14 j -= 1 15 return dp[-1]
Here float('inf')
represents an infinity (a large number that's greater than any other number), and dp[-1]
fetches the last element in the dp
list (same as dp.back()
in C++).
Java Solution
1 2java 3class Solution { 4 public int minHeightShelves(int[][] books, int shelf_width) { 5 int n = books.length; 6 int[] dp = new int[n+1]; 7 dp[0] = 0; 8 for(int i = 1; i <= n; i++){ 9 int width = books[i-1][0]; 10 int height = books[i-1][1]; 11 dp[i] = dp[i-1] + height; 12 for(int j = i-1; j > 0 && width + books[j-1][0] <= shelf_width; j--){ 13 height = Math.max(height, books[j-1][1]); 14 width += books[j-1][0]; 15 dp[i] = Math.min(dp[i], dp[j-1] + height); 16 } 17 } 18 return dp[n]; 19 } 20}
JavaScript Solution
1 2javascript 3var minHeightShelves = function(books, shelf_width) { 4 const dp = Array(books.length + 1).fill(Number.MAX_SAFE_INTEGER); 5 dp[0] = 0; 6 for(let i=0; i<books.length; i++) { 7 let width = 0; 8 let maxHeight = 0; 9 for(let j=i; j>=0; j--) { 10 const [thickness, height] = books[j]; 11 width += thickness; 12 if(width > shelf_width) break; 13 maxHeight = Math.max(maxHeight, height); 14 dp[i+1] = Math.min(dp[i+1], dp[j] + maxHeight); 15 } 16 } 17 return dp[dp.length-1]; 18};
This javascript solutionn uses MAX_SAFE_INTEGER
a constant in JavaScript to represent maximum numeric value possible in JavaScript.
C++ Solution
1
2cpp
3class Solution {
4public:
5 int minHeightShelves(vector<vector<int>>& books, int shelf_width) {
6 vector<int> dp(books.size() + 1, INT_MAX);
7 dp[0] = 0;
8 for (int i = 0; i < books.size(); ++i) {
9 int width = 0;
10 int height = 0;
11 for(int j = i; j >=0; --j) {
12 width += books[j][0];
13 height = max(height, books[j][1]);
14 if(width > shelf_width)
15 break;
16 dp[i+1] = min(dp[i+1], dp[j] + height);
17 }
18 }
19 return dp.back();
20 }
21};
This C++ uses INT_MAX
, a constant in C++ that returns the maximum value that can be hold by an integer.
C# Solution
1 2csharp 3public class Solution { 4 public int MinHeightShelves(int[][] books, int shelf_width) { 5 int n = books.Length; 6 int[] dp = new int[n+1]; 7 dp[0] = 0; 8 for(int i = 1; i <= n; i++){ 9 int width = books[i-1][0]; 10 int height = books[i-1][1]; 11 dp[i] = dp[i-1] + height; 12 for(int j = i-1; j > 0 && width + books[j-1][0] <= shelf_width; j--){ 13 height = Math.Max(height, books[j-1][1]); 14 width += books[j-1][0]; 15 dp[i] = Math.Min(dp[i], dp[j-1] + height); 16 } 17 } 18 return dp[n]; 19 } 20}
In all these solutions, time complexity is O(n^2) because we have nested for loop running n times each, and the space complexity is O(n) for the DP array. This algorithm can be considered a variation of the Knapsack problem which is a common problem in combinatorial optimization.## Ruby Solution
1 2ruby 3class Solution 4 def minHeightShelves(books, shelf_width) 5 dp = Array.new(books.length + 1, Float::INFINITY) 6 dp[0] = 0 7 books.each_with_index do |book, i| 8 width, max_height = 0, 0 9 j = i 10 while j >= 0 && width + books[j][0] <= shelf_width 11 width += books[j][0] 12 max_height = [max_height, books[j][1]].max 13 dp[i+1] = [dp[i+1], dp[j] + max_height].min 14 j -= 1 15 end 16 end 17 dp[-1] 18 end 19end
This Ruby solution uses Float::INFINITY
to represent an extremely large positive number which suffices for a sufficiently high initial height of shelves. Iterating from the back, for each book, we try to fit it onto the same shelf as the previous one and keep track of the current width and the maximum height. The ternary [max_height, books[j][1]].max
is an equivalent for Math.max()
in other languages and the ternary [dp[i+1], dp[j] + max_height].min
is equivalent to Math.min()
.
Finally, when we have gone through all the books, the smallest total height is stored in dp[-1]
. With the time complexity of O(n^2) and space complexity of O(n), this forward-thinking dynamic programming solution is efficient for the problem.
Wrapping Up
Now with solutions in Python, Java, JavaScript, C++, C# and Ruby, you have multiple perspectives to solving this problem. It involves careful arrangement of the given books, each with a different height and thickness, onto the shelves making sure the given order is maintained.
Remember, when solving such dynamic programming problems the key is to articulate the base case and logic for optimal substructure correctly. Once you've got the hang of these aspects, coding the solutions should fall into place with enough practice! Happy coding!
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.