Skip to main content

1105. Filling Bookcase Shelves

medium

Place books in order on shelves of fixed width; each shelf's height is the tallest book on it. Minimize total height. 1D-shape DP where each state inspects backward to find every valid 'last shelf'.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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. Return the minimum possible height that the total bookshelf can be after placing shelves in this manner.

Constraints

  • 1 <= books.length <= 1000
  • 1 <= thickness, height <= shelfWidth <= 1000

Examples

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Books are placed in order — so for the i-th book, the choice is which earlier book j started the current bottom shelf.

Hint 2

dp[i] = min total height to place the first i books.

Hint 3

For each i, walk back from j = i down to 1: track the rolling width and the max height in [j, i]. If width <= shelfWidth, dp[i] = min(dp[i], dp[j-1] + maxHeight).

Hint 4

Base dp[0] = 0. O(n^2) in the worst case (books with tiny thickness).

Solution approach

Reveal approach

Bottom-up DP. dp[i] is the minimum total bookcase height after placing the first i books. Base dp[0] = 0. For each i from 1 to n, sweep backward from j = i down to 1, tracking width = sum of thickness for books[j-1..i-1] and maxH = max of heights for the same range. While width <= shelfWidth, dp[i] = min(dp[i], dp[j-1] + maxH); stop the inner loop when width exceeds shelfWidth. Return dp[n]. The inner sweep tries every possible 'first book on the current bottom shelf' choice. Time O(n^2) in the worst case, far less in practice when books are wider relative to shelfWidth. The 2D framing is (i, j) — current end and the index where the last shelf began — with j tracked implicitly by the inner loop.

Complexity

Time
O(n^2)
Space
O(n)

Related patterns

  • dynamic-programming
  • partition-dp

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google

Practice these live with InterviewChamp.AI

Drill Filling Bookcase Shelves and 2D Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →