1105. Filling Bookcase Shelves Solution

The problem

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

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.

Python

from typing import List

class Solution:
    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:
        n = len(books)
        dp = [0] + [float('inf')] * n
        for i in range(1, n + 1):
            width = height = 0
            for j in range(i, 0, -1):
                width += books[j - 1][0]
                if width &gt; shelfWidth: break
                height = max(height, books[j - 1][1])
                dp[i] = min(dp[i], dp[j - 1] + height)
        return dp[n]

Java

import java.util.*;

class Solution {
    public int minHeightShelves(int[][] books, int shelfWidth) {
        int n = books.length;
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i &lt;= n; i++) {
            int width = 0, height = 0;
            for (int j = i; j > 0; j--) {
                width += books[j - 1][0];
                if (width &gt; shelfWidth) break;
                height = Math.max(height, books[j - 1][1]);
                dp[i] = Math.min(dp[i], dp[j - 1] + height);
            }
        }
        return dp[n];
    }
}

C++

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    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 &lt;= n; i++) {
            int width = 0, height = 0;
            for (int j = i; j > 0; j--) {
                width += books[j - 1][0];
                if (width &gt; 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) {
    const n = books.length;
    const dp = Array(n + 1).fill(Infinity);
    dp[0] = 0;
    for (let i = 1; i &lt;= n; i++) {
        let width = 0, height = 0;
        for (let j = i; j > 0; j--) {
            width += books[j - 1][0];
            if (width &gt; shelfWidth) break;
            height = Math.max(height, books[j - 1][1]);
            dp[i] = Math.min(dp[i], dp[j - 1] + height);
        }
    }
    return dp[n];
};

#include <stdio.h>
#include <limits.h>

int minHeightShelves(int books[][2], int booksSize, int* booksColSize, int shelfWidth) {
    int dp[booksSize + 1];
    dp[0] = 0;
    for (int i = 1; i &lt;= booksSize; i++) {
        int width = 0, height = 0;
        dp[i] = INT_MAX;
        for (int j = i; j > 0; j--) {
            width += books[j - 1][0];
            if (width &gt; shelfWidth) break;
            height = height &gt; books[j - 1][1] ? height : books[j - 1][1];
            if (dp[j-1] + height &lt; dp[i]) dp[i] = dp[j-1] + height;
        }
    }
    return dp[booksSize];
}

public class Solution {
    public int MinHeightShelves(int[][] books, int shelfWidth) {
        int n = books.Length;
        int[] dp = new int[n + 1];
        Array.Fill(dp, int.MaxValue);
        dp[0] = 0;
        for (int i = 1; i &lt;= n; i++) {
            int width = 0, height = 0;
            for (int j = i; j > 0; j--) {
                width += books[j - 1][0];
                if (width &gt; shelfWidth) break;
                height = Math.Max(height, books[j - 1][1]);
                dp[i] = Math.Min(dp[i], dp[j - 1] + height);
            }
        }
        return dp[n];
    }
}

The Python approach makes use of a list to store dp values. For each book, we attempt every possible placement and select the one yielding the least height increase. The process takes into account all combinations up to the shelf width constraint.

Complexity

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

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.

Python

from typing import List

class Solution:
    def minHeightShelves(self, books: List[List[int]], shelfWidth: int) -> int:
        memo = {}
        def dfs(pos):
            if pos == len(books):
                return 0
            if pos in memo:
                return memo[pos]
            width, height = 0, 0
            minHeight = float('inf')
            for i in range(pos, len(books)):
                width += books[i][0]
                if width &gt; shelfWidth:
                    break
                height = max(height, books[i][1])
                minHeight = min(minHeight, height + dfs(i + 1))
            memo[pos] = minHeight
            return minHeight
        return dfs(0)

Java

import java.util.*;

class Solution {
    public int minHeightShelves(int[][] books, int shelfWidth) {
        int n = books.length;
        int[] dp = new int[n];
        Arrays.fill(dp, -1);
        return helper(books, shelfWidth, 0, dp);
    }
    private int helper(int[][] books, int shelfWidth, int pos, int[] dp) {
        if (pos == books.length) return 0;
        if (dp[pos] != -1) return dp[pos];
        int width = 0, height = 0, minHeight = Integer.MAX_VALUE;
        for (int i = pos; i &lt; books.length; i++) {
            width += books[i][0];
            if (width &gt; shelfWidth) break;
            height = Math.max(height, books[i][1]);
            minHeight = Math.min(minHeight, height + helper(books, shelfWidth, i + 1, dp));
        }
        dp[pos] = minHeight;
        return minHeight;
    }
}

C++

#include <string>
#include <vector>
#include <limits>
using namespace std;

class Solution {
    int dfs(vector<vector<int>> & books, int shelfWidth, int pos, vector<int> & dp) {
        if (pos == books.size()) return 0;
        if (dp[pos] != -1) return dp[pos];
        int width = 0, height = 0, minHeight = INT_MAX;
        for (int i = pos; i &lt; books.size(); i++) {
            width += books[i][0];
            if (width &gt; shelfWidth) break;
            height = max(height, books[i][1]);
            minHeight = min(minHeight, height + dfs(books, shelfWidth, i + 1, dp));
        }
        dp[pos] = minHeight;
        return minHeight;
    }
public:
    int minHeightShelves(vector<math>> books, int shelfWidth) {
        vector<int> dp(books.size(), -1);
        return dfs(books, shelfWidth, 0, dp);
    }
};

JavaScript

var minHeightShelves = function(books, shelfWidth) {
    let dp = Array(books.length).fill(-1);
    function dfs(pos) {
        if (pos === books.length) return 0;
        if (dp[pos] !== -1) return dp[pos];
        let width = 0, height = 0;
        let minHeight = Infinity;
        for (let i = pos; i &lt; books.length; i++) {
            width += books[i][0];
            if (width &gt; shelfWidth) break;
            height = Math.max(height, books[i][1]);
            minHeight = Math.min(minHeight, height + dfs(i + 1));
        }
        dp[pos] = minHeight;
        return minHeight;
    }
    return dfs(0);
};

#include <string>
#include <stdio.h>
#include <limits.h>

int minHeightShelvesRec(int books[][2], int n, int shelfWidth, int i, int dp[]) {
    if (i == n) return 0;
    if (dp[i] != -1) return dp[i];
    int width = 0, height = 0, minHeight = INT_MAX;
    for (int j = i; j &lt; n; j++) {
        width += books[j][0];
        if (width &gt; shelfWidth) break;
        height = height &gt; books[j][1] ? height : books[j][1];
        int nextHeight = minHeightShelvesRec(books, n, shelfWidth, j+1, dp);
        if (nextHeight + height &lt; minHeight) minHeight = nextHeight + height;
    }
    dp[i] = minHeight;
    return dp[i];
}

int minHeightShelves(int books[][2], int booksSize, int* booksColSize, int shelfWidth) {
    int dp[booksSize];
    memset(dp, -1, sizeof(dp));
    return minHeightShelvesRec(books, booksSize, shelfWidth, 0, dp);
}

using System;

public class Solution {
    public int MinHeightShelves(int[][] books, int shelfWidth) {
        int[] dp = new int[books.Length];
        Array.Fill(dp, -1);
        return MinHeight(books, shelfWidth, 0, dp);
    }
    private int MinHeight(int[][] books, int shelfWidth, int pos, int[] dp) {
        if (pos == books.Length) return 0;
        if (dp[pos] != -1) return dp[pos];
        int width = 0, height = 0, minHeight = int.MaxValue;
        for (int i = pos; i &lt; books.Length; i++) {
            width += books[i][0];
            if (width &gt; shelfWidth) break;
            height = Math.Max(height, books[i][1]);
            minHeight = Math.Min(minHeight, height + MinHeight(books, shelfWidth, i + 1, dp));
        }
        dp[pos] = minHeight;
        return minHeight;
    }
}

This Python solution combines DFS with a memo dictionary for caching. Each call attempts to add more books to the shelf, heuristically deciding based on both results: extending the current shelf or starting anew. This setup fosters optimal path choice leading to minimized bookcase height.

Complexity

Time Complexity: O(n^2)
Space Complexity: O(n), noted for recursive cache and call depth.

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.

TypeScript

function minHeightShelves(books: number[][], shelfWidth: number): number {
    const n = books.length;
    const f = new Array(n + 1).fill(0);
    for (let i = 1; i <= n; ++i) {
        let [w, h] = books[i - 1];
        f[i] = f[i - 1] + h;
        for (let j = i - 1; j > 0; --j) {
            w += books[j - 1][0];
            if (w > shelfWidth) {
                break;
            }
            h = Math.max(h, books[j - 1][1]);
            f[i] = Math.min(f[i], f[j - 1] + h);
        }
    }
    return f[n];
}

func minHeightShelves(books [][]int, shelfWidth int) int {
	n := len(books)
	f := make([]int, n+1)
	for i := 1; i <= n; i++ {
		w, h := books[i-1][0], books[i-1][1]
		f[i] = f[i-1] + h
		for j := i - 1; j > 0; j-- {
			w += books[j-1][0]
			if w > shelfWidth {
				break
			}
			h = max(h, books[j-1][1])
			f[i] = min(f[i], f[j-1]+h)
		}
	}
	return f[n]
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Dynamic Programming Approach	Time Complexity: O(n^2) Space Complexity: O(n)
Backtracking with Memoization	Time Complexity: O(n^2) Space Complexity: O(n), noted for recursive cache and call depth.
Dynamic Programming	–

Complexity analysis

Approach	Time	Space	When 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

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.

Filling Bookcase Shelves solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming Approach

Approach 2: Backtracking with Memoization

Approach 3: Dynamic Programming

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Filling Bookcase Shelves solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming Approach

Approach 2: Backtracking with Memoization

Approach 3: Dynamic Programming

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems