Problem Description

You have an array of books where each book is represented as books[i] = [thickness_i, height_i], indicating the thickness and height of the i-th book. You also have a bookshelf with a fixed width shelfWidth.

Your task is to place these books onto the bookshelf shelves following these rules:

1. Books must be placed in the given order - you cannot rearrange the sequence of books
2. For each shelf level:
   • You can place consecutive books on the same shelf as long as the sum of their thicknesses doesn't exceed shelfWidth
   • The height added to the total bookshelf is the maximum height among all books on that shelf level
3. Continue creating new shelf levels until all books are placed

For example, if you have 5 books in order and shelfWidth allows:

• Books 1 and 2 might fit together on the first shelf (contributing the max height of these two books)
• Book 3 goes on the second shelf alone (contributing its height)
• Books 4 and 5 fit together on the third shelf (contributing the max height of these two books)

The goal is to find the minimum possible total height of the bookshelf after placing all books.

The dynamic programming solution works by:

• f[i] represents the minimum height needed to place the first i books
• For each book position i, it considers:
  • Placing the book on a new shelf: f[i] = f[i-1] + current_book_height
  • Placing the book with previous books on the same shelf (if width permits): try grouping with j-1, j, ..., i-1 books and take the minimum height configuration

Intuition

The key insight is that we need to make decisions about where to "break" the sequence of books into different shelves. Since books must be placed in order, this becomes a problem of finding optimal partition points.

Think of it this way: when we're about to place book i, we have two choices:

1. Start a new shelf with this book
2. Try to fit it on the same shelf as some previous books

This naturally leads to a dynamic programming approach where we build up the solution for placing books 1 to i based on solutions for smaller subproblems.

For each book position i, we ask: "What's the minimum height if I've placed the first i books?" To answer this, we need to determine which books should share the last shelf with book i.

The clever part is working backwards from book i. We can try putting book i alone on a new shelf, or we can try combining it with book i-1, or with books i-2 and i-1, and so on - as long as the total thickness doesn't exceed shelfWidth.

Why work backwards? Because we want to explore all valid configurations for the last shelf. Starting from book i and looking back, we accumulate thickness and track the maximum height. Once the thickness exceeds shelfWidth, we know we can't fit any more books on this shelf.

For each valid configuration of the last shelf (say books j through i), the total height would be:

• The minimum height to place books 1 through j-1 (which we've already computed)
• Plus the height of the current shelf (maximum height among books j through i)

We take the minimum across all these valid configurations. This ensures we find the optimal way to arrange books that minimizes the total height while respecting the ordering and width constraints.

Learn more about Dynamic Programming patterns.

Solution Approach

We implement a dynamic programming solution using a 1D array f where f[i] represents the minimum height needed to place the first i books.

Initialization:

• Create array f of size n + 1 where n is the number of books
• Set f[0] = 0 (no books means zero height)

Main Algorithm:

For each book i (1-indexed), we iterate through all books and compute f[i]:

1. Extract current book properties:

   • w = books[i-1][0] (thickness)
   • h = books[i-1][1] (height)

2. Initial assumption: Place book i on a new shelf

   • f[i] = f[i-1] + h

3. Try combining with previous books:

   • Iterate backwards from book j = i-1 down to j = 1
   • For each book j:
     • Add its thickness to current shelf: w += books[j-1][0]
     • If w > shelfWidth, break (can't fit more books)
     • Update shelf height: h = max(h, books[j-1][1])
     • Update minimum: f[i] = min(f[i], f[j-1] + h)

The backwards iteration logic: When we consider placing books j through i on the same shelf:

• f[j-1] gives us the minimum height for books 1 through j-1
• h tracks the maximum height among books j through i
• The total height would be f[j-1] + h

Time Complexity: O(n²) where n is the number of books, as for each book we potentially check all previous books.

Space Complexity: O(n) for the DP array.

The final answer is f[n], which represents the minimum height after optimally placing all n books.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Input:

• books = [[1,3], [2,4], [3,2]] (format: [thickness, height])
• shelfWidth = 6

We need to find the minimum total height to place these 3 books in order.

Setup:

• Initialize DP array: f = [0, 0, 0, 0]
• f[0] = 0 (base case: no books = 0 height)

Processing Book 1 [1,3]:

• Current book: thickness=1, height=3
• Only option: place on new shelf
• f[1] = f[0] + 3 = 0 + 3 = 3
• Result: f = [0, 3, 0, 0]

Processing Book 2 [2,4]:

• Current book: thickness=2, height=4
• Option 1: Place on new shelf
  • f[2] = f[1] + 4 = 3 + 4 = 7
• Option 2: Combine with Book 1
  • Combined thickness: 1 + 2 = 3 ≤ 6 ✓
  • Shelf height: max(3, 4) = 4
  • f[2] = f[0] + 4 = 0 + 4 = 4
• Take minimum: f[2] = min(7, 4) = 4
• Result: f = [0, 3, 4, 0]

Processing Book 3 [3,2]:

• Current book: thickness=3, height=2
• Option 1: Place on new shelf
  • f[3] = f[2] + 2 = 4 + 2 = 6
• Option 2: Combine with Book 2
  • Combined thickness: 2 + 3 = 5 ≤ 6 ✓
  • Shelf height: max(4, 2) = 4
  • f[3] = f[1] + 4 = 3 + 4 = 7
• Option 3: Combine with Books 2 and 1
  • Combined thickness: 1 + 2 + 3 = 6 ≤ 6 ✓
  • Shelf height: max(3, 4, 2) = 4
  • f[3] = f[0] + 4 = 0 + 4 = 4
• Take minimum: f[3] = min(6, 7, 4) = 4
• Result: f = [0, 3, 4, 4]

Final Answer: f[3] = 4

The optimal arrangement places all three books on the same shelf (since their combined thickness is exactly 6), resulting in a total height of 4 (the maximum height among all books).

Solution Implementation

Time and Space Complexity

The time complexity of this algorithm is O(n²), where n is the length of the books array. This is because:

• The outer loop iterates through all n books (from index 1 to n)
• For each book at position i, the inner loop iterates backwards from i-1 to 1 in the worst case
• This creates a nested loop structure where for each of the n iterations of the outer loop, we potentially have up to i-1 iterations of the inner loop
• The total number of operations is approximately 1 + 2 + 3 + ... + (n-1) = n(n-1)/2, which simplifies to O(n²)

The space complexity is O(n). The algorithm uses:

• An array f of size n+1 to store the dynamic programming states, which requires O(n+1) = O(n) space
• A few additional variables (i, j, w, h) that use constant space O(1)
• The overall space complexity is therefore O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Errors with Book Indexing

The most common mistake occurs when mixing 0-based array indexing with 1-based DP array indexing. Since books is 0-indexed but dp[i] represents the first i books (1-indexed), developers often incorrectly access book properties.

Incorrect approach:

for i in range(1, n + 1):
    dp[i] = dp[i - 1] + books[i][1]  # Wrong! books[i] is out of bounds when i = n

Correct approach:

for i in range(1, n + 1):
    dp[i] = dp[i - 1] + books[i - 1][1]  # Correct: books[i-1] for the i-th book

2. Incorrect Width Accumulation Order

When iterating backwards to try different shelf combinations, developers might add the current book's width multiple times or forget to include it initially.

Incorrect approach:

for i in range(1, n + 1):
    dp[i] = dp[i - 1] + books[i - 1][1]
    cumulative_width = 0  # Wrong! Missing current book's width
    max_height = 0  # Wrong! Missing current book's height
  
    for j in range(i - 1, 0, -1):
        cumulative_width += books[j - 1][0]
        # This never includes book i's width!

Correct approach:

for i in range(1, n + 1):
    width, height = books[i - 1]
    dp[i] = dp[i - 1] + height
    cumulative_width = width  # Start with current book
    max_height = height  # Start with current book's height
  
    for j in range(i - 1, 0, -1):
        cumulative_width += books[j - 1][0]
        # Now correctly accumulates all books from j to i

3. Forgetting to Update Maximum Height

When grouping books on the same shelf, some implementations forget to continuously update the maximum height as they add more books to the shelf.

Incorrect approach:

for j in range(i - 1, 0, -1):
    cumulative_width += books[j - 1][0]
    if cumulative_width > shelfWidth:
        break
    # Forgot to update max_height!
    dp[i] = min(dp[i], dp[j - 1] + height)  # Uses original height only

Correct approach:

for j in range(i - 1, 0, -1):
    cumulative_width += books[j - 1][0]
    if cumulative_width > shelfWidth:
        break
    max_height = max(max_height, books[j - 1][1])  # Update shelf height
    dp[i] = min(dp[i], dp[j - 1] + max_height)  # Use updated max_height

4. Breaking Too Early in the Inner Loop

Some implementations might use continue instead of break when the shelf width is exceeded, leading to incorrect results by skipping only one iteration instead of stopping entirely.

Incorrect approach:

for j in range(i - 1, 0, -1):
    cumulative_width += books[j - 1][0]
    if cumulative_width > shelfWidth:
        continue  # Wrong! This skips current j but continues with j-1
    max_height = max(max_height, books[j - 1][1])
    dp[i] = min(dp[i], dp[j - 1] + max_height)

Correct approach:

for j in range(i - 1, 0, -1):
    cumulative_width += books[j - 1][0]
    if cumulative_width > shelfWidth:
        break  # Correct: Stop trying to add more books to this shelf
    max_height = max(max_height, books[j - 1][1])
    dp[i] = min(dp[i], dp[j - 1] + max_height)