Domain 2MediumMEDIUM

Filling Bookcase Shelves

LeetCode problem 1105: Filling Bookcase Shelves (medium).

Domain: medium•Updated: 2026-09-08
#Dynamic Programming

Problem Breakdown

We are given a sequence of books where each book has a specific thickness and height. We need to stack these books onto shelves with a fixed maximum total width (shelf_width). The key constraints are:

  1. Order Preservation: Books must be placed in the exact order they appear in the input list (contiguous segments).
  2. Shelf Height Rule: A shelf’s height is determined by the tallest book on it, regardless of how many books fit horizontally.
  3. Objective: Minimize the total vertical space used by stacking all shelves sequentially until no more books remain.

Inputs: books (List[List[int]]), shelf_width (int).
Output: Integer representing minimum total height.

Implicit Constraints & Edge Cases:

  • Books cannot be skipped or reordered; we must partition the array into contiguous subarrays.
  • If a single book’s thickness exceeds shelf_width, it is impossible per constraints, but given problem guarantees (books[i][0] <= shelf_width), this won’t happen.
  • Empty input isn’t possible due to constraints (N≥1N \ge 1).

Intuition

A brute-force approach would try every possible way to split the books into shelves (partitioning a sequence of length NN can have up to 2N−12^{N-1} partitions), leading to exponential time complexity. This is insufficient for N=1000N=1000.

However, this problem exhibits optimal substructure and overlapping subproblems, characteristic of Dynamic Programming (DP).

  • To solve the problem for n books, we need to know the minimum height required to place the first i books. Let’s call this state dp[i].
  • When considering book at index i, we have two choices: either start a new shelf with just this book (or extend an existing one), or append it to a previous group on the current shelf.
  • Since shelves are filled left-to-right, when calculating for book i as part of a new shelf ending at i, we can look back from i-1 down to find all valid contiguous groups that fit within shelf_width.

Approach

We will use an array dp where dp[i] represents the minimum height required to store the first i books (indices 0 through i-1). Initialize dp[0] = 0 and others as infinity.

For each book index i from 1 to n:

  1. Assume we start a new shelf with just this current book (books[i-1]). The cost is at least the height of this single book plus whatever was needed for previous books (dp[i-1] + max_height_of_current_shelf).
  2. Iterate backwards from the current book index i to find how many preceding books can fit on the same shelf as the current one.
  3. Maintain a running sum of widths and maximum height encountered while iterating leftwards (from i-1 down to -1).
  4. If adding a previous book keeps us within shelf_width, update our DP state:
    dp[i] = min(dp[i], dp[j+1] + current_shelf_max_height) where j is the index of the last added book (conceptually, if we are looking at range [k...i-1], previous cost was dp[k]).
  5. If adding a book exceeds width capacity, stop iterating backwards for this state because any further books to the left will only increase total width.

Complexity Analysis

  • Time: O(N2)O(N^2). We have an outer loop running NN times and an inner backward loop that runs at most NN times (bounded by shelf capacity). Given constraints (N≤1000N \le 1000), this is roughly 10610^6 operations, well within limits.
  • Space: O(N)O(N) for the DP array to store intermediate results.

Solution

def minHeightShelves(books: List[List[int]], shelf_width: int) -> int:
    n = len(books)
    # dp[i] stores min height for first i books (indices 0..i-1)
    dp = [float('inf')] * (n + 1)
    
    # Base case: 0 books require 0 height
    dp[0] = 0
    
    for i in range(1, n + 1):
        current_book_idx = i - 1
        
        width_left = shelf_width
        max_h = 0
        
        # Iterate backwards to find the start of the last shelf ending at book[i-1]
        j = current_book_idx
        while j >= 0:
            if books[j][0] <= width_left:
                width_left -= books[j][0]
                max_h = max(max_h, books[j][1])
                
                # If we include books from index (j+1) to i-1 on this shelf,
                # the previous state was after placing j+1 books. 
                # dp[i] is min of current best and new option:
                if dp[j + 1] != float('inf'):
                    dp[i] = min(dp[i], dp[j + 1] + max_h)
            else:
                # Cannot fit this book on the shelf, stop expanding leftwards.
                break
                
    return dp[n]

Edge Cases Handled

  • Single Book: The loop runs once for i=1, inner loop checks if it fits (guaranteed by constraints), sets height to its own max height. Correct.
  • All Books Fit on One Shelf: Inner loop iterates all books backwards, width sum stays within limit, final DP state reflects just the maximum book height of that single shelf plus 0 previous cost. Correct.
  • Forced New Shelves: If a specific book is thick or tall enough to force a break in inner loop logic (width exceeded), dp[i] correctly falls back on splitting at earlier points via minimization.