1105. Filling Bookcase Shelves

Problem Description

In this problem, we're given an array books where each books[i] represents the ith book with its thickness and height as [thicknessi, heighti]. We also have a bookshelf of a fixed width, shelfWidth. The goal is to arrange the books in such a way that they all fit on the shelves while maintaining their original order and minimizing the total height of the bookshelf.

The process for placing books onto the bookshelf is as follows:

Books are taken from the array in the same order they are given and placed onto the shelf.
A group of books can be placed on the same shelf if their total thickness does not exceed the shelf width.
Once a shelf is filled (or can't fit the next book without exceeding shelfWidth), a new shelf is started above it.
The height of each shelf is determined by the tallest book on that shelf.
The process continues until all books are placed on the shelf.
The total height of the bookshelf is the sum of the heights of each individual shelf.

The challenge is to determine the least total height of the bookshelf after all the books are placed according to the rules.

Intuition

For the solution, dynamic programming is used to keep track of the optimal height at each step. The key idea is to iteratively determine the minimum height required to arrange all books up to the current one. Here's a step-by-step breakdown:

Initialize a dynamic programming array f of n + 1 elements, where n is the number of books.
For each book, calculate the minimum height if this book starts a new shelf by adding its height to the minimum height found for all previous books.
Then, for the same book, consider the possibility of placing it on the same shelf as the previous book(s). For each cluster of books that can fit together on the same shelf without exceeding shelfWidth, calculate the minimum height needed if these books shared a shelf.
To do this, iterate backwards from the current book and keep adding the thicknesses of each previous book until the total thickness exceeds shelfWidth.
As you go along, keep track of the maximum height of the books in the current shelf arrangement since that determines the height of the shelf.
Update the minimum height for the current set of books as the lesser of the existing minimum height or the height required if these books share a shelf, which is the sum of maximum book height on this shelf and the minimum height found before starting this shelf.
After calculating for all books, the last element in the f array will contain the minimum possible height of the bookshelf.

The optimization comes from recognizing that the best height for a set of books up to the ith book is either on a new shelf or combined with some recent books on the same shelf to minimize the height added. By comparing each possibility, we guarantee we're finding the optimal combination at each step.

Learn more about Dynamic Programming patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Solution Approach

The solution provided uses dynamic programming as its primary algorithmic strategy. This involves breaking a larger problem down into smaller subproblems and storing the results of those subproblems to avoid redundant computations. Here's how the algorithm works step by step:

An array f of length n + 1 is initialized with zeroes, where n is the number of books. The array f will hold the minimum height of the bookshelf when the last book placed is the ith book (f[i]).
We loop through each book, and for each book (w, h):
- We set f[i] to f[i - 1] + h by default, assuming the book (w, h) starts a new shelf, where i is the current book's index in one-based notation. This means we add the height of this book to the total height we had before adding this book.
- We then consider the possibility of placing each book in reverse order onto the same shelf, starting by adding the second last book and so on, until we either run out of books or the total thickness would exceed the shelfWidth. For each combination, we update the current maximum height of the books on the shelf and check if the minimum total height f[i] can be improved by placing the current book on the same shelf as the previous one(s).
Within the inner loop, we are performing the following computations:
- Increment the total thickness w by the thickness of the previous book (starting from the current book and moving backwards).
- If w exceeds shelfWidth, we break out of the loop as we can't add any more books to the current shelf.
- Otherwise, we update the current maximum height h to be the maximum of the current h and the height of the book we're trying to add to the shelf.
- Then, we calculate the minimum total height f[i] by comparing its current value with the sum of the maximum shelf height h and the minimum height f[j - 1] that can be achieved before adding the books currently considered on the shelf. We then select the minimum of those two values.
This loop continues for all books, and once we have considered all possible placements for each book, the last element of f, f[n], holds the minimum total height of the bookshelf, which is the final answer.

The data structure used is a simple array (f), which holds the best solution to subproblems (best bookshelf height given a certain number of books). By iterating over the possible placements for each book, we are effectively employing a bottom-up dynamic programming approach.

In summary, the algorithm builds upon previous solutions to maintain the minimum height required at each step, while considering new book placements, to achieve an overall optimal arrangement with respect to the total height.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Example Walkthrough

Let's illustrate the solution approach with a small example. Suppose we have an array of books:

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

and we want to arrange the books on a bookshelf with a shelf width of 4. We follow the solution approach using dynamic programming.

We initialize an array f with length n + 1 where n is the number of books. In our case, n=4, so f = [0, 0, 0, 0, 0]. This array will store the minimum total height after the ith book has been placed.
Start with the first book [1, 1]. If it starts a new shelf, the total height is just the height of this book, so f[1] = 1.
Now place the second book [2, 3]. If it starts a new shelf, the minimum total height after this book is f[1] + height(second book) = 1 + 3 = 4, so f[2] = 4. However, since its thickness (2) plus the thickness of the first book (1) does not exceed the shelfWidth (4), we also check if we can place it on the same shelf as the first book. This would keep the shelf height as the maximum height of the first two books, which is 3. So, f[2] remains 3 since 3 < 4.
Now consider the third book [2, 3]. If it starts a new shelf, then the minimum total height is f[2] + height(third book) = 3 + 3 = 6. But can it fit with the second book on the same shelf? The total thickness would be 2(second book) + 2(third book) = 4, which is equal to shelfWidth, and the height would be the taller book's height, which is 3, so the total height is still 3 + 3 = 6. Now, can we fit the first and third books together instead? The total thickness would be 1(first book) + 2(third book) = 3, which is less than shelfWidth, and we find the max height among the first and third books to be 3. So, the minimum height becomes f[3] = 1(original height of the first shelf with only the first book) + 3(height of the third book) = 4. Since 4 < 6, we update f[3] = 4.
Finally, the fourth book [1, 2]. Starting a new shelf would result in f[3] + height(fourth book) = 4 + 2 = 6. Can it fit on the same shelf as the third? No, because 2(third book) + 1(fourth book) = 3, and if we include the second book, the total thickness 2(second book) + 2(third book) + 1(fourth book) = 5 exceeds the shelf width. So, it must start a new shelf. As the fourth book is shorter than the third, it doesn't alter our already calculated f[3]. However, we check if the first and fourth book can share a shelf, and they can as their combined thickness is 2, and the shelf height will be determined by the fourth book 2. So, f[4] would be 1(height of the first shelf) + 2(height of the fourth book) = 3. The total minimum height f[4] is 3.

So, by following the dynamic programming approach, we've determined that the books can be arranged in the smallest total height which is 3. The arrangement would be: first and fourth book on the bottom shelf and second and third books on the shelf above.

Solution Implementation

1class Solution:
2    def minHeightShelves(self, books: List[List[int]], shelf_width: int) -> int:
3        # Number of books
4        num_books = len(books)
5
6        # List to store the minimum height at each point
7        min_height = [0] * (num_books + 1)
8
9        # Loop through each book
10        for i, (width, height) in enumerate(books, 1):
11            # Initially, put the book on a new shelf
12            min_height[i] = min_height[i - 1] + height
13
14            # Initialize the total width of the current shelf
15            total_width = width
16          
17            # Try placing previous books on the same shelf and check
18            # if it can minimize the total height of the shelves
19            for j in range(i - 1, 0, -1):
20                # Add the width of the book j to the total width
21                total_width += books[j - 1][0]
22
23                # If the total width exceeds the shelf width, we can't place more books on the same shelf
24                if total_width > shelf_width:
25                    break
26
27                # Update the height of the current shelf to be the maximum book height on the shelf
28                height = max(height, books[j - 1][1])
29
30                # Update the minimum height if placing the book on the current shelf results in less height
31                min_height[i] = min(min_height[i], min_height[j - 1] + height)
32
33        # After placing all the books, the last element in min_height stores the minimized total height
34        return min_height[num_books]
35

1class Solution {
2    public int minHeightShelves(int[][] books, int shelfWidth) {
3        int numOfBooks = books.length;
4        // 'dp' array will store the minimum height for the first 'i' books
5        int[] dp = new int[numOfBooks + 1];
6      
7        for (int i = 1; i <= numOfBooks; ++i) {
8            // Initial width and height for the current book
9            int currentWidth = books[i - 1][0];
10            int currentHeight = books[i - 1][1];
11          
12            // Place current book on a new shelf
13            dp[i] = dp[i - 1] + currentHeight;
14          
15            // Try placing previous books with the current one on the same shelf
16            for (int j = i - 1; j > 0; --j) {
17                currentWidth += books[j - 1][0]; // Accumulate width
18              
19                // If accumulated width exceeds shelfWidth, stop trying to place more books
20                if (currentWidth > shelfWidth) {
21                    break;
22                }
23              
24                // Update the current height to be the tallest book in the current placement
25                currentHeight = Math.max(currentHeight, books[j - 1][1]);
26                // Calculate the minimum height if this set of books were on the same shelf,
27                // comparing with the previous minimum height and updating it if necessary
28                dp[i] = Math.min(dp[i], dp[j - 1] + currentHeight);
29            }
30        }
31      
32        // Return the minimum height to place all the books
33        return dp[numOfBooks];
34    }
35}
36

1class Solution {
2public:
3    int minHeightShelves(vector<vector<int>>& books, int shelfWidth) {
4        // Total number of books
5        int numBooks = books.size();
6      
7        // Initialize the dynamic programming array which will store the minimum height for the first i books
8        vector<int> dp(numBooks + 1);
9      
10        // Base case: no books means the shelves have a height of 0
11        dp[0] = 0;
12      
13        // Loop through each book
14        for (int i = 1; i <= numBooks; ++i) {
15            // Width and height of the current book
16            int currentWidth = books[i - 1][0], currentHeight = books[i - 1][1];
17          
18            // By default the minimum height after adding this book is its height plus the height of previous shelves without this book
19            dp[i] = dp[i - 1] + currentHeight;
20          
21            // Try to place previous books on the same shelf with the current book to minimize the total height
22            for (int j = i - 1; j > 0; --j) {
23                // Accumulate the width with the previous book
24                currentWidth += books[j - 1][0];
25              
26                // Break the loop if adding another book exceeds the shelf width
27                if (currentWidth > shelfWidth) {
28                    break;
29                }
30              
31                // Update the current shelf's height based on the tallest book on this shelf
32                currentHeight = max(currentHeight, books[j - 1][1]);
33              
34                // Determine the minimum height if this shelf configuration is used (place as many books as possible on the current shelf)
35                dp[i] = min(dp[i], dp[j - 1] + currentHeight);
36            }
37        }
38      
39        // The last element in dp will have the minimum height by placing all books
40        return dp[numBooks];
41    }
42};
43

1function minHeightShelves(books: number[][], shelfWidth: number): number {
2    const numBooks = books.length;
3    // Array 'dp' to store the minimum height at each index
4    const dp = new Array(numBooks + 1).fill(0);
5
6    for (let i = 1; i <= numBooks; ++i) {
7        let [currentWidth, currentHeight] = books[i - 1];
8        // Initialize the height of the current shelf
9        dp[i] = dp[i - 1] + currentHeight;
10      
11        // Iterate through the previous books to find minimum height for the current shelf
12        for (let j = i - 1; j > 0; --j) {
13            // Accumulate width of books on the current shelf
14            currentWidth += books[j - 1][0];  
15            if (currentWidth > shelfWidth) {
16                // If width exceeds the shelf width, stop the loop
17                break;
18            }
19          
20            // Calculate the max height on the current shelf
21            currentHeight = Math.max(currentHeight, books[j - 1][1]);
22            // Update 'dp' with the minimum height by comparing it with the height of the previous arrangement plus current shelf height
23            dp[i] = Math.min(dp[i], dp[j - 1] + currentHeight);
24        }
25    }
26
27    // Return the minimum height needed to place all books
28    return dp[numBooks];
29}
30

Not Sure What to Study? Take the 2-min Quiz：

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12

1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

<=, left, right<, left, right<=, right, left<, right, left

I don’t know

Time and Space Complexity

The given Python function calculates the minimum height of a shelf that can contain all the books, given a list of book dimensions and the width of the shelf. It uses dynamic programming to solve the problem.

Time Complexity:

The outer loop iterates over each book (n iterations, where n is the number of books). Inside the outer loop, there is an inner loop that iterates backward from the current book index i to 1. This inner loop runs at most i times, and since it decreases progressively, it results in a series that sums up roughly to n(n + 1)/2 in the worst case. The operations within the inner loop are constant-time operations.

Consequently, the overall time complexity is O(n^2).

Space Complexity:

For space, an array of size n + 1 is used to store the running minimum heights, where n is the number of books. No other space-consuming structures are used. Thus, the space complexity is linear.

Hence, the space complexity is O(n).

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

Fast Track Your Learning with Our Quick Skills Quiz:

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

dp[i] = dp[i - 1] + dp[i - 2]dp[i] = dp[i - 1] + 1dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]dp[i] = dp[i - 1]

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

1105. Filling Bookcase Shelves

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity:

Space Complexity:

Recommended Readings