Skip to main content
Talentd

Filling Bookcase Shelves - Solution & Explanation

MediumArrayDynamic Programming22 min readAsked at: Amazon, Google, Flipkart +2
Practice this problem

Problem Statement

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.

  • 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 <= thicknessi <= shelfWidth <= 1000
  • 1 <= heighti <= 1000

Approach Overview

Problem Overview: You are given books in a fixed order, where each book has a width and height. Place them on shelves with a maximum shelf width so that the total height of the bookcase is minimized. Books must stay in order, and each shelf’s height equals the tallest book placed on it.

Approach 1: Backtracking with Memoization (Top‑Down DP) (Time: O(n²), Space: O(n))

This approach models the problem as a decision at every book index: either continue placing books on the current shelf or start a new shelf. From index i, iterate forward while the cumulative width stays within shelfWidth. Track the maximum height of the current shelf and recursively compute the minimum height for the remaining books. Memoization stores results for each starting index so the same state is not recomputed repeatedly.

The key insight is that each recursive call represents the minimum height achievable from a specific book index onward. Without memoization the recursion becomes exponential, but caching reduces it to quadratic because each index explores at most n forward placements. This approach is intuitive when you first recognize the problem as overlapping subproblems, a classic pattern in dynamic programming.

Approach 2: Dynamic Programming (Bottom‑Up) (Time: O(n²), Space: O(n))

The bottom‑up dynamic programming version builds the solution iteratively. Define dp[i] as the minimum total height required to place the first i books. For each position i, try placing book i on the current shelf together with previous books. Iterate backward from i while accumulating shelf width and tracking the maximum height of books on that shelf.

For each valid grouping, update dp[i] using dp[j-1] + currentShelfHeight. This effectively decides where the previous shelf ended. The algorithm checks every contiguous group of books that can fit within the width limit, making the complexity quadratic. The data is stored in an array, and the recurrence structure follows standard optimization patterns in dynamic programming.

This approach is typically preferred in production or interviews because it avoids recursion overhead and expresses the state transition clearly. Each state depends only on earlier states, making the logic deterministic and easy to debug.

Recommended for interviews: The bottom‑up dynamic programming solution is what most interviewers expect. It demonstrates that you can convert a recursive idea into an efficient iterative DP. Explaining the top‑down memoized version first can still help show how you derived the recurrence, but implementing the iterative DP shows stronger problem‑solving maturity.

Approach 1: Dynamic Programming Approach

This approach involves using dynamic programming to decide the optimal cutting of shelves using the given books. Let df[i] be the minimum height for placing the first i books. For each book i, you consider ending a new shelf at book i but try every starting point from j = i to find the best cut. The key here is to use a nested loop to calculate the minimum height iteratively.

This solution uses an integer array df of size booksSize + 1, where each element df[i] represents the minimum height of the bookshelf containing the first i books. Two nested loops check each combination to find the minimum. The outer loop selects to end a shelf with the i-th book, while the inner loop determines the start of that shelf.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2), where n is the number of books.
Space Complexity: O(n), due to the use of extra space for the dp array.

Try this approach in the editor →

Approach 2: Backtracking with Memoization

This strategy uses a recursive backtracking approach augmented with memoization to avoid redundant calculations. By attempting to place books on shelves recursively and caching computed heights, it achieves optimal placement efficiently. This method provides a balance between direct computation and saved results.

The C code recursively tries to place each book on a new shelf or the current shelf. It uses a memoization array dp to store computed minimum heights for the subproblems, avoiding recomputation. This recursion explores every possibility and chooses the arrangement yielding the minimum height incrementally.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2), primarily constrained due to state saving over recursion calls
Space Complexity: O(n), requires extra space for memoization.

Try this approach in the editor →

Approach 3: Dynamic Programming

We define f[i] as the minimum height for placing the first i books, initially f[0] = 0, and the answer is f[n].

Consider f[i], the last book is books[i - 1], its thickness is w, and its height is h.

  • If this book is placed on a new layer alone, then f[i] = f[i - 1] + h;
  • If this book can be placed on the same layer with the last few books in front, we enumerate the first book books[j-1] on the same layer from back to front, where j \in [1, i - 1], accumulate the thickness of the book to w, if w > shelfWidth, it means that books[j-1] can no longer be placed on the same layer with books[i-1], stop enumeration; otherwise, we update the maximum height h = max(h, books[j-1][1]) of the current layer, then f[i] = min(f[i], f[j - 1] + h).

The final answer is f[n].

The time complexity is O(n^2), and the space complexity is O(n). Here, n is the length of the array books.

Code

PythonJavaC++GoTypeScriptC#

Python

Java

C++

Go

TypeScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming Approach

Time Complexity: O(n^2), where n is the number of books.
Space Complexity: O(n), due to the use of extra space for the dp array.

Backtracking with Memoization

Time Complexity: O(n^2), primarily constrained due to state saving over recursion calls
Space Complexity: O(n), requires extra space for memoization.

Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Backtracking with Memoization (Top‑Down DP)O(n²)O(n)Good for understanding the recurrence and modeling the decision process recursively
Dynamic Programming (Bottom‑Up)O(n²)O(n)Preferred in interviews and production due to predictable iteration and no recursion overhead

Video Solution

Filling Bookcase Shelves - Leetcode 1105 - Python • NeetCodeIO • 20,907 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Filling Bookcase Shelves with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays