How do you solve Filling Bookcase Shelves on LeetCode?

Filling Bookcase Shelves (LeetCode #1105) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n²) time complexity and O(n) space complexity. Key insight: Dynamic programming helps avoid recalculating heights for previously considered books.

What is the time complexity of Filling Bookcase Shelves?

The optimal solution for Filling Bookcase Shelves runs in O(n²) time and uses O(n) space. The time complexity remains O(n²) due to the nested loop, but we save results in dp, reducing redundant calculations.

What is the brute force solution for Filling Bookcase Shelves?

The brute force approach for Filling Bookcase Shelves is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach tries every possible way to place books on the shelves. It checks all combinations of books for each shelf, calculating the total height for each configuration. The optimal Optimal Solution approach improves this to O(n²).

What algorithm or data structure is used to solve Filling Bookcase Shelves?

Filling Bookcase Shelves uses the following concepts: Array, Dynamic Programming. The recommended patterns to study are: Dynamic Programming, Greedy Algorithms.

What are the interview tips for Filling Bookcase Shelves?

Explain your thought process clearly when discussing dynamic programming. Be prepared to discuss edge cases, such as when all books fit on one shelf. Practice breaking down the problem into smaller parts before coding.

What are common mistakes when solving Filling Bookcase Shelves?

Not considering the order of books when placing them on shelves. Failing to correctly update the maximum height for the current shelf.

#1105

Filling Bookcase Shelves

Medium

ArrayDynamic ProgrammingDynamic ProgrammingGreedy Algorithms

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n²)
Space	O(1)	O(n)

💡

Intuition

Time O(n²)Space O(n)

The optimal solution uses dynamic programming to store the minimum height needed for each book index. By building on previously computed results, we avoid redundant calculations.

⚙️

Algorithm

3 steps

1Step 1: Initialize a dp array where dp[i] represents the minimum height of the bookshelf for the first i books.
2Step 2: Iterate through each book and for each book, check all previous books to see if they can fit on the same shelf.
3Step 3: Update the dp array with the minimum height found by considering the maximum height of the current shelf.

solution.py12 lines

1def minHeightShelves(books, shelfWidth):
2    dp = [0] * (len(books) + 1)
3    for i in range(1, len(books) + 1):
4        total_thickness = 0
5        max_height = 0
6        for j in range(i - 1, -1, -1):
7            total_thickness += books[j][0]
8            if total_thickness > shelfWidth:
9                break
10            max_height = max(max_height, books[j][1])
11            dp[i] = min(dp[i], dp[j] + max_height)
12    return dp[len(books)]

ℹ

Complexity note: The time complexity remains O(n²) due to the nested loop, but we save results in dp, reducing redundant calculations.

1Dynamic programming helps avoid recalculating heights for previously considered books.
2Understanding the constraints of shelfWidth is crucial for optimizing book placement.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.