Is Filling Bookcase Shelves easy or hard?

Filling Bookcase Shelves is classified as a Medium problem on LeetCode. The challenge comes from recognizing the dynamic programming structure and correctly evaluating all valid groups of books that can share a shelf.

Filling Bookcase Shelves Python/Java solution

Both Python and Java implementations follow the same bottom‑up DP logic. Maintain a dp array and for each book iterate backward while the shelf width limit allows, updating the minimal total height using dp transitions.

How to solve Filling Bookcase Shelves in O(n)?

An exact O(n) solution is generally not achievable because each book may need to be evaluated with multiple previous books to determine valid shelf groupings. The accepted optimal approach is O(n²) dynamic programming, which checks all feasible shelf partitions efficiently.

What is the best approach for Filling Bookcase Shelves?

The optimal approach uses Dynamic Programming with O(n²) time and O(n) space. Define dp[i] as the minimum height required to place the first i books. For each book i, iterate backward to group books on the same shelf while tracking width and maximum height, updating dp[i] with the best configuration.

Is Filling Bookcase Shelves asked at Google/Amazon/Meta?

Dynamic programming partition problems like Filling Bookcase Shelves frequently appear in interviews at companies such as Amazon, Google, and Meta. The problem tests state definition, recurrence design, and efficient iteration over subarrays.

What data structure is used in Filling Bookcase Shelves?

The primary data structure is a dynamic programming array where dp[i] stores the minimum height needed for the first i books. During computation, variables track cumulative shelf width and maximum height while iterating through the books array.

What is the time complexity of Filling Bookcase Shelves?

The standard dynamic programming solution runs in O(n²) time. For every book index, the algorithm iterates backward to check how many previous books can fit on the same shelf while maintaining the width constraint.

Description Hints 1 Solution Video 19:17

1105. Filling Bookcase Shelves

Medium68.7% acceptance5 companies

You are given an array books where books[i] = [thickness_i, height_i] indicates the thickness and height of the i^th 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.

For example, if we have an ordered list of 5 books, we might place the first and second book onto the first shelf, the third book on the second shelf, and the fourth and fifth book on the last shelf.

Return the minimum possible height that the total bookshelf can be after placing shelves in this manner.

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

Constraints:

1 <= books.length <= 1000
1 <= thickness_i <= shelfWidth <= 1000
1 <= height_i <= 1000

Asked at 5 companies

6Sense Flipkart

Google Amazon Bloomberg

Topics

Array Dynamic Programming

Hints open one at a time

Hint 1

Use dynamic programming: dp(i) will be the answer to the problem for books[i:].

19:17

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]]
4

Input

[[1,3],[2,4],[3,2]]
6

Your code is saved on this device.Solution