LeetCode 1105 - Filling Bookcase Shelves

The problem asks us to arrange a sequence of books on a bookshelf with multiple shelves while minimizing the total height of the bookshelf. Each book is described by its thickness and height, and the books must be placed in the given order.

leetcodemediumarraydynamic-programming

LeetCode Problem 1105

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming

Solution

Problem Understanding

The problem asks us to arrange a sequence of books on a bookshelf with multiple shelves while minimizing the total height of the bookshelf. Each book is described by its thickness and height, and the books must be placed in the given order. Each shelf has a fixed width limit, and the sum of the thicknesses of books on a single shelf cannot exceed this width. Once a shelf is filled, its height contributes to the total bookshelf height, which is determined by the tallest book on that shelf.

The input consists of an array books where books[i] = [thickness, height] and an integer shelfWidth. The output is a single integer representing the minimal possible total height of the bookshelf.

Constraints indicate that books.length can be up to 1000 and thicknesses and heights can be up to 1000, meaning that any brute-force solution must be carefully considered for efficiency. Important edge cases include books with maximum possible thickness, books that individually equal the shelf width, and books of varying heights that affect shelf height calculations. The problem guarantees at least one book, so we do not need to handle an empty input array.

Approaches

The brute-force approach is to try every possible partition of books into shelves. For each book, we can either start a new shelf or add it to the current shelf if the width allows. This guarantees correctness but is infeasible for large inputs because the number of possible partitions grows exponentially with the number of books, leading to O(2^n) time complexity.

The key insight for a more efficient solution is to use dynamic programming. We define dp[i] as the minimum total height for arranging the first i books. To compute dp[i], we consider all possible previous positions j < i where the j+1 to i books could fit on the same shelf. We then take the minimum height across all such partitions. This approach reduces the problem from exponential to polynomial time because we systematically compute solutions for all subproblems and reuse them.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(n) Tries every combination of shelf partitions; infeasible for n = 1000
Dynamic Programming O(n^2) O(n) Uses DP to build minimal height incrementally; feasible for n ≤ 1000

Algorithm Walkthrough

  1. Initialize a DP array dp of length n + 1 where dp[i] represents the minimal total height for the first i books. Set dp[0] = 0 because zero books require zero height.
  2. Iterate through each book index i from 1 to n. For each i, we attempt to place books j to i-1 on the current shelf, where j goes from i-1 down to 0.
  3. Maintain variables width to track the sum of thicknesses and height to track the tallest book on the current shelf. Start with width = 0 and height = 0.
  4. For each candidate j, add the thickness of books[j] to width. If width exceeds shelfWidth, break because no more books can fit on the shelf.
  5. Update height to be the maximum of current height and books[j][1].
  6. Update dp[i] as the minimum of its current value and dp[j] + height, representing placing books j to i-1 on the current shelf.
  7. After iterating through all i, return dp[n] as the minimal total bookshelf height.

The key invariant is that dp[i] always stores the minimal height for the first i books, ensuring that by the time we reach dp[n], we have considered all valid shelf partitions.

Python Solution

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 = 0
            height = 0
            for j in range(i - 1, -1, -1):
                width += books[j][0]
                if width > shelfWidth:
                    break
                height = max(height, books[j][1])
                dp[i] = min(dp[i], dp[j] + height)
        
        return dp[n]

The Python implementation initializes a DP array and iterates through each book to compute the minimal total height. It considers all possible previous books that could fit on the current shelf and updates the DP array accordingly. This ensures an optimal solution in O(n^2) time.

Go Solution

func minHeightShelves(books [][]int, shelfWidth int) int {
    n := len(books)
    dp := make([]int, n+1)
    for i := 1; i <= n; i++ {
        dp[i] = 1 << 60
    }

    for i := 1; i <= n; i++ {
        width := 0
        height := 0
        for j := i - 1; j >= 0; j-- {
            width += books[j][0]
            if width > shelfWidth {
                break
            }
            if books[j][1] > height {
                height = books[j][1]
            }
            if dp[j]+height < dp[i] {
                dp[i] = dp[j] + height
            }
        }
    }

    return dp[n]
}

The Go implementation follows the same DP logic. We initialize dp with a large number for comparison, track the width and height for the current shelf, and update the DP array accordingly. Go handles slices efficiently, and integer overflow is not an issue with the problem constraints.

Worked Examples

Example 1:

books = [[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]], shelfWidth = 4

Trace table:

i j width height dp[i] update
1 0 1 1 dp[1] = dp[0]+1 = 1
2 1 2 3 dp[2] = dp[1]+3 = 4
3 2 2 3 dp[3] = min(dp[2]+3, dp[1]+3) = 4
4 3 1 1 dp[4] = dp[3]+1 = 5
5 4 1 1 dp[5] = dp[4]+1 = 6
6 5 1 1 dp[6] = dp[5]+1 = 6
7 6 1 2 dp[7] = dp[6]+2 = 6

Result: dp[7] = 6

Example 2:

books = [[1,3],[2,4],[3,2]], shelfWidth = 6

Trace table:

i j width height dp[i] update
1 0 1 3 dp[1] = 3
2 1 2 4 dp[2] = dp[0]+4 = 4
3 2 3 2 dp[3] = dp[1]+2 = 5, dp[0]+4 = 4

Result: dp[3] = 4

Complexity Analysis

Measure Complexity Explanation
Time O(n^2) For each book, we may examine all previous books to find a valid shelf partition
Space O(n) We maintain a DP array of length n+1

The DP solution is feasible for n ≤ 1000, and all operations are within acceptable limits for competitive programming.

Test Cases

# Provided examples
assert Solution().minHeightShelves([[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]], 4) == 6  # example 1
assert Solution().minHeightShelves([[1,3],[2,4],[3,2]], 6) == 4  # example 2

# Boundary cases
assert Solution().minHeightShelves([[1,1]], 1) == 1  # single book
assert Solution().minHeightShelves([[1,2],[1,3],[1,4]], 1) == 9  # each book on separate shelf
assert Solution().minHeightShelves([[2,1],[2,2],[2,3]], 6) == 3  # all fit on one shelf

# Stress cases
assert Solution().minHeightShelves([[1,1000]]*1000, 1000) == 1000  # all books same height
assert Solution().minHeightShelves([[1000,1]]*1000