Filling Bookcase Shelves

Medium

Asked by:

36 views

Topics:

ArraysDynamic Programming

You are given an array books where books[i] = [thickness_i, height_i] indicates the thickness and height of the i^th book. You are also given an integer shelfWidth.

We want to place these books in order onto bookcase shelves that have a total width shelfWidth.

We choose some of the books to place on this shelf such that the sum of their thickness is less than or equal to shelfWidth, then build another level of the shelf of the bookcase so that the total height of the bookcase has increased by the maximum height of the books we just put down. We repeat this process until there are no more books to place.

Note that at each step of the above process, the order of the books we place is the same order as the given sequence of books.

For example, if we have an ordered list of 5 books, we might place the first and second book onto the first shelf, the third book on the second shelf, and the fourth and fifth book on the last shelf.

Return the minimum possible height that the total bookshelf can be after placing shelves in this manner.

Example 1:

Input: books = [[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]], shelfWidth = 4
Output: 6
Explanation:
The sum of the heights of the 3 shelves is 1 + 3 + 2 = 6.
Notice that book number 2 does not have to be on the first shelf.

Example 2:

Input: books = [[1,3],[2,4],[3,2]], shelfWidth = 6
Output: 4

Constraints:

1 <= books.length <= 1000
1 <= thickness_i <= shelfWidth <= 1000
1 <= height_i <= 1000

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the width of each book and the shelf width? Could a book's width be greater than the shelf width?
Can the widths of the books be zero or negative numbers?
If it's impossible to shelve all the books, what should the function return? Should I return -1, or throw an exception?
Is the order of the books fixed, or can I reorder them to minimize the number of shelves used?
Does minimizing the height of the shelves have priority over minimizing the number of shelves?

Brute Force Solution

Approach

The brute force method for arranging books on shelves involves exploring every single possible configuration. We'll try every combination of how to place books on each shelf, ensuring no shelf exceeds its capacity. We'll then compare all valid arrangements to find the best one based on a cost calculation.

Here's how the algorithm would work step-by-step:

Consider putting only the first book on the first shelf.
Consider putting the first two books on the first shelf, then the first three, and so on, until you have tried putting all the books on the first shelf.
For each of these options, check if the total width of the books on the shelf is less than or equal to the shelf's capacity.
If a shelf's width exceeds its capacity, discard that option.
For each valid arrangement of the first shelf, repeat the process for the second shelf, starting with the next book after those on the first shelf.
Continue this process for each subsequent shelf until all books have been placed.
Each complete arrangement represents a possible solution. Calculate the 'cost' of each possible solution (for instance, the total height of the shelves).
Compare the costs of all possible solutions and select the arrangement with the lowest cost as the best arrangement.

Code Implementation

def filling_bookcase_shelves_brute_force(books, shelf_width):
    number_of_books = len(books)

    def calculate_minimum_height(book_index, current_arrangement):
        # If all books are placed, calculate the total height
        if book_index == number_of_books:
            total_height = 0
            for shelf in current_arrangement:
                max_height = 0
                for book_index_on_shelf in shelf:
                    max_height = max(max_height, books[book_index_on_shelf][1])
                total_height += max_height
            return total_height

        minimum_height = float('inf')

        # Try adding books to the last shelf or create a new one
        for books_to_add in range(1, number_of_books - book_index + 1):
            new_shelf = []
            shelf_width_used = 0
            valid_arrangement = True

            # Check if adding books exceeds shelf width
            for i in range(book_index, book_index + books_to_add):
                shelf_width_used += books[i][0]
                if shelf_width_used > shelf_width:
                    valid_arrangement = False
                    break
                new_shelf.append(i)

            if valid_arrangement:
                updated_arrangement = current_arrangement + [new_shelf]
                height = calculate_minimum_height(book_index + books_to_add, updated_arrangement)
                minimum_height = min(minimum_height, height)

        return minimum_height

    # The initial arrangement has zero shelves
    initial_arrangement = []
    result = calculate_minimum_height(0, initial_arrangement)

    return result

Big(O) Analysis

Time Complexity

O(2^n) – The brute force approach explores all possible arrangements of books on shelves. For each book, we have a choice: either place it on the current shelf or start a new shelf. With n books, this results in 2^n possible arrangements. We evaluate each arrangement to calculate its cost and choose the minimum, hence the time complexity is O(2^n).

Space Complexity

O(N) – The brute force method explores every possible configuration of books on shelves using recursion. Each recursive call represents placing a certain number of books on a shelf, and the maximum depth of the recursion would be proportional to the number of books, N, in the worst case (each book on a new shelf). This creates a call stack that could grow up to a depth of N. Therefore, the auxiliary space complexity is O(N) due to the recursion depth.

Optimal Solution

Approach

We want to figure out the smallest possible height for the bookcase shelves. We'll use a clever way of building up the solution, always picking the best shelf height we've seen so far. This prevents us from exploring a huge number of useless arrangements.

Here's how the algorithm would work step-by-step:

Imagine we're deciding which books to put on the first shelf. We'll consider all possible combinations of books starting from the first one.
For each combination of books, we check if their total width is less than or equal to the shelf width. If it is, we calculate the height of that shelf (which is just the height of the tallest book on that shelf).
We remember the best total bookcase height we've found so far for placing those books on the first shelf. This means, what's the height of the first shelf PLUS the best possible height for the remaining books.
Now, we move on to the next book, and repeat the process. We consider all possible combinations of books starting from that next book for the first shelf and remember the best bookcase height so far.
We continue this process until we reach the end of the list of books. The best bookcase height we've found at the end is the answer.

Code Implementation

def filling_bookcase_shelves(books, shelf_width):    number_of_books = len(books)
    dp = [0] * (number_of_books + 1)

    for i in range(1, number_of_books + 1):
        # Initialize the minimum height to a large value.
        minimum_height = float('inf')
        current_width = 0
        current_height = 0

        for j in range(i - 1, -1, -1):
            current_width += books[j][0]
            current_height = max(current_height, books[j][1])

            # If the current books fit on the shelf
            if current_width <= shelf_width:
                # Calculate the total height and update minimum if needed
                minimum_height = min(minimum_height, current_height + dp[j])
            else:
                # If the books don't fit, break the inner loop
                break

        # Store the minimum height for the first i books
        dp[i] = minimum_height

        # dp[i] holds the minimum height of the bookcase with i books.

    return dp[number_of_books]

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each book, considering it as the starting point for the first shelf. For each starting book, it explores all possible combinations of subsequent books to fit on that shelf. In the worst-case scenario, for a given starting book, we might iterate through the remaining n-1 books. Thus, the total number of operations can be approximated as n * (n-1), where n is the number of books. This simplifies to O(n²).

Space Complexity

O(N) – The algorithm described uses dynamic programming implicitly. To store the best total bookcase height found so far for placing the first i books, it needs an array (or similar data structure) of size N, where N is the number of books. This array allows us to store and reuse intermediate results, specifically the minimum height for the bookcase up to a certain book. Therefore, the auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
Empty books array.	Return 0, as no shelves are needed for an empty list of books.
shelfWidth is zero or negative.	Return an error or throw an exception, as shelf width must be positive.
A single book whose width exceeds shelfWidth.	Return an error or throw an exception, as the book cannot fit on any shelf.
All books have zero height.	The minimum shelf height will be zero, leading to a potentially incorrect minimum overall height; handle by ensuring a non-zero height selection.
All books have the same width.	This could lead to a skewed distribution and potentially suboptimal shelf arrangement; the algorithm should still produce a correct answer but could benefit from optimization.
The total width of all books is less than shelfWidth.	Place all books on a single shelf, returning the height of the tallest book.
Integer overflow when calculating shelf width sums (language-specific).	Use appropriate data types (e.g., long) or error checking to prevent integer overflows.
Maximum number of books (input size constraints).	Dynamic programming solutions might consume considerable memory; ensure memory usage remains within acceptable limits or consider iterative approaches for optimization.

Empty books array.

How to Handle:

Return 0, as no shelves are needed for an empty list of books.

shelfWidth is zero or negative.

How to Handle:

Return an error or throw an exception, as shelf width must be positive.

A single book whose width exceeds shelfWidth.

How to Handle:

Return an error or throw an exception, as the book cannot fit on any shelf.

All books have zero height.

How to Handle:

The minimum shelf height will be zero, leading to a potentially incorrect minimum overall height; handle by ensuring a non-zero height selection.

All books have the same width.

How to Handle:

This could lead to a skewed distribution and potentially suboptimal shelf arrangement; the algorithm should still produce a correct answer but could benefit from optimization.

The total width of all books is less than shelfWidth.

How to Handle:

Place all books on a single shelf, returning the height of the tallest book.

Integer overflow when calculating shelf width sums (language-specific).

How to Handle:

Use appropriate data types (e.g., long) or error checking to prevent integer overflows.

Maximum number of books (input size constraints).

How to Handle:

Dynamic programming solutions might consume considerable memory; ensure memory usage remains within acceptable limits or consider iterative approaches for optimization.