Filling Bookcase Shelves

Medium
1479.

Filling Bookcase Shelves

Filling Bookcase Shelves is a medium coding problem on arrays and dynamic programming, asked in Amazon, Google and Microsoft interviews.

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 <= 1000
  • 1 <= thickness_i <= shelfWidth <= 1000
  • 1 <= height_i <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} books
 * @param {number} shelfWidth
 * @return {number}
 */
var minHeightShelves = function(books, shelfWidth) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 1000
  • 1 <= thickness_i <= shelfWidth <= 1000
  • 1 <= height_i <= 1000

Hints for Filling Bookcase Shelves

  1. Hint 1

    Think about which books share the last shelf: always a suffix of the books placed so far.

  2. Hint 2

    Let dp[i] be the minimum height for the first i books.

  3. Hint 3

    For dp[i], extend the last shelf backwards from book i while 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

  1. dp[0] = 0.
  2. For i = 1..n: walk j from i down to 1, adding book j-1 to the last shelf; stop once the width exceeds shelfWidth.
  3. While walking, keep the shelf's maximum height h and update dp[i] = min(dp[i], dp[j-1] + h).
  4. 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