Filling Bookcase Shelves — Solution in Python, Java & C++
Filling Bookcase Shelves solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Filling Bookcase Shelves is a medium coding problem on arrays and dynamic programming, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
books[i] = [thickness_i, height_i] describes the i-th book. The books must go onto a bookcase in the given order: fill a shelf with a consecutive run of books, then start a new shelf below it for the next run, and so on.
The books on one shelf may have total thickness at most shelfWidth. A shelf is as tall as its tallest book, and the bookcase is as tall as the sum of its shelves' heights.
Return the minimum possible height of the bookcase.
Example 1
Input: books = [[2,5],[3,1],[1,4]], shelfWidth = 4
Output: 9
Explanation: Shelf 1 holds `[2,5]` (height 5); shelf 2 holds `[3,1]` and `[1,4]` (width 4, height 4).
Example 2
Input: books = [[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]], shelfWidth = 4
Output: 6
Explanation: Shelves `[1,1]`, then `[2,3],[2,3]`, then the last four books: 1 + 3 + 2.
Example 3
Input: books = [[3,7]], shelfWidth = 5
Output: 7
Constraints
1 <= books.length <= 10001 <= thickness_i <= shelfWidth <= 10001 <= height_i <= 1000
Hints for Filling Bookcase Shelves
Hint 1
Think about which books share the last shelf: always a suffix of the books placed so far.
Hint 2
Let
dp[i]be the minimum height for the firstibooks.Hint 3
For
dp[i], extend the last shelf backwards from bookiwhile the width allows, tracking its tallest book:dp[i] = min(dp[j] + maxHeight(j..i-1)).
How to solve Filling Bookcase Shelves
Because the order is fixed, a bookcase is just a way to cut the sequence into consecutive runs whose widths fit. The last run is some suffix, which gives a one-dimensional DP over prefixes.
Approach
dp[0] = 0.- For
i = 1..n: walkjfromidown to 1, adding bookj-1to the last shelf; stop once the width exceedsshelfWidth. - While walking, keep the shelf's maximum height
hand updatedp[i] = min(dp[i], dp[j-1] + h). - Return
dp[n].
Why it works
Any arrangement of the first i books ends with a shelf holding books j-1..i-1 for some j, and the shelves above it form an arrangement of the first j-1 books, whose best height is dp[j-1]. Trying every feasible j therefore finds the optimum.
Complexity
- Time —
O(n²) (O(n · shelfWidth) when thicknesses are at least 1) - Space —
O(n)
Pitfalls
- Books cannot be reordered — this is not a bin-packing problem.
- Stop extending the shelf as soon as the width overflows; earlier books only add width.
- Every single book fits on a shelf by the constraints, so
dp[i]is always finite.
Reference solution
Python
from typing import List
def minHeightShelves(books: List[List[int]], shelfWidth: int) -> int:
n = len(books)
INF = 10**18
dp = [0] + [INF] * n
for i in range(1, n + 1):
width = 0
height = 0
j = i
while j >= 1:
width += books[j - 1][0]
if width > shelfWidth:
break
if books[j - 1][1] > height:
height = books[j - 1][1]
if dp[j - 1] + height < dp[i]:
dp[i] = dp[j - 1] + height
j -= 1
return dp[n]Java
public static int minHeightShelves(int[][] books, int shelfWidth) {
int n = books.length;
int[] dp = new int[n + 1];
for (int i = 1; i <= n; i++) {
dp[i] = Integer.MAX_VALUE;
int width = 0, height = 0;
for (int j = i; j >= 1; j--) {
width += books[j - 1][0];
if (width > shelfWidth) break;
height = Math.max(height, books[j - 1][1]);
dp[i] = Math.min(dp[i], dp[j - 1] + height);
}
}
return dp[n];
}C++
int minHeightShelves(vector<vector<int>>& books, int shelfWidth) {
int n = books.size();
vector<int> dp(n + 1, INT_MAX);
dp[0] = 0;
for (int i = 1; i <= n; i++) {
int width = 0, height = 0;
for (int j = i; j >= 1; j--) {
width += books[j - 1][0];
if (width > shelfWidth) break;
height = max(height, books[j - 1][1]);
dp[i] = min(dp[i], dp[j - 1] + height);
}
}
return dp[n];
}JavaScript
var minHeightShelves = function(books, shelfWidth) {
var n = books.length;
var dp = new Array(n + 1).fill(Infinity);
dp[0] = 0;
for (var i = 1; i <= n; i++) {
var width = 0, height = 0;
for (var j = i; j >= 1; j--) {
width += books[j - 1][0];
if (width > shelfWidth) break;
if (books[j - 1][1] > height) height = books[j - 1][1];
if (dp[j - 1] + height < dp[i]) dp[i] = dp[j - 1] + height;
}
}
return dp[n];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming