Skip to main content

1105. Filling Bookcase Shelves

medium

Place books in order on shelves of bounded width to minimize total height. A 1D DP — for each book, sweep backward to compose the current 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 bookcase can be after placing shelves in this manner.

Constraints

  • 1 <= books.length <= 1000
  • 1 <= thicknessi <= shelfWidth <= 1000
  • 1 <= heighti <= 1000

Examples

Example 1

Input
books = [[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,1]], 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 must stay in order — no permutation allowed.

Hint 2

dp[i] = minimum total height using the first i books. For each i sweep back j from i-1 down: accumulate thickness and track max height while thickness fits in shelfWidth.

Hint 3

dp[i] = min over valid j of dp[j] + max-height-from-j+1-to-i.

Solution approach

Reveal approach

Books are ordered, so the decision at each book is only where to start a new shelf. Let dp[i] = minimum total bookcase height using the first i books. dp[0] = 0. For each i from 1 to n, sweep j from i down to 1 accumulating shelf_width (sum of thicknesses for books j..i) and shelf_height (max height for books j..i). While shelf_width <= shelfWidth, update dp[i] = min(dp[i], dp[j - 1] + shelf_height). Break out when shelf_width exceeds the cap. Return dp[n]. The reverse sweep over j lets you grow the current shelf one book at a time, recomputing max height in O(1) per step. O(n^2) time worst case, O(n) space.

Complexity

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

Related patterns

  • dynamic-programming

Related problems

Asked at

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

  • Amazon

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →