Maximum Number of Books You Can Take

Hard

Asked by:

6 views

Topics:

ArraysDynamic ProgrammingStacks

You are given a 0-indexed integer array books of length n where books[i] denotes the number of books on the i^th shelf. You are also given an integer shelfWidth denoting the maximum number of shelves you can use.

In one step, you can select any contiguous range of shelves and move each book from the selected shelves onto one new shelf. Formally, you can pick two integers i and j where 0 <= i <= j < n, you take all the books from shelves books[i], books[i+1], ..., books[j] and place them on one new shelf.

Return the maximum number of shelves you can have such that no shelf contains more than shelfWidth books.

Example 1:

Input: books = [2,3,4,5], shelfWidth = 6
Output: 2
Explanation: We can first move the books from shelves 0, 1, 2 onto one shelf. Then move the books from shelf 3 onto another shelf.
We have 2 shelves in total each holding not more than 6 books. Note that we could have also moved the books from shelves 2 and 3 onto one shelf. Then move the books from shelves 0 and 1 onto another shelf. This results in 2 shelves each holding not more than 6 books.

Example 2:

Input: books = [4,6,2,3], shelfWidth = 4
Output: 1
Explanation: We can move the books from shelves 2 and 3 onto one shelf. Then one of the shelves 0 or 1 has more than 4 books, so we cannot put any more books onto shelves. Therefore, the maximum number of shelves is 1.

Constraints:

1 <= books.length <= 10⁵
1 <= books[i] <= 10⁵
1 <= shelfWidth <= 10⁵

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 number of books in each stack?
Can the number of books in a stack be zero?
Is it possible to have an empty input list of book counts?
If it's not possible to take any books at all according to the rules, what value should I return?
If there are multiple valid ways to choose the maximum number of books, is any valid solution acceptable?

Brute Force Solution

Approach

The brute force approach involves trying every possible combination of books we could potentially take. We explore each selection of books, calculate the total 'niceness' value and check if it follows the rules. Finally, we pick the selection with the highest 'niceness' that is valid.

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

Start by considering taking no books at all. This is one possible selection.
Then, consider taking only the first book, then only the second book, and so on until we consider only taking the last book. These are all single-book selections.
Next, consider taking every possible combination of two books. For example, the first and second book, the first and third book, the second and fifth book, and so on.
Continue this process, considering all possible combinations of three books, four books, and so on, until you consider taking all the books.
For each possible combination of books, calculate the total 'niceness' value of the selected books.
Also, for each combination, check if the sequence of books you selected satisfies the rule that each book should be no taller than its neighbors.
Keep track of the combination of books with the highest total 'niceness' value that also satisfies the rule about book heights.
Once you have considered all possible combinations, the selection with the highest total 'niceness' and satisfying the rule will be the best one.

Code Implementation

def max_books_brute_force(niceness_values, height_values):
    number_of_books = len(niceness_values)
    max_niceness = 0

    # Iterate through all possible combinations of books
    for i in range(1 << number_of_books):
        current_selection = []
        current_niceness = 0

        for j in range(number_of_books):
            # Check if the j-th book is included in the current combination
            if (i >> j) & 1:
                current_selection.append(j)
                current_niceness += niceness_values[j]

        # Check if the current selection is valid
        is_valid = True
        if len(current_selection) > 0:
            for k in range(len(current_selection)):
                book_index = current_selection[k]

                # Check if each book is no taller than its neighbors
                if k > 0:
                    previous_book_index = current_selection[k - 1]
                    if height_values[book_index] > height_values[previous_book_index]:
                        is_valid = False
                        break
                if k < len(current_selection) - 1:
                    next_book_index = current_selection[k + 1]
                    if height_values[book_index] > height_values[next_book_index]:
                        is_valid = False
                        break

        #Update maximum niceness if the selection is valid
        if is_valid:
            max_niceness = max(max_niceness, current_niceness)

    return max_niceness

Big(O) Analysis

Time Complexity

O(2^n) – The brute force approach generates all possible subsets of the input array of size n. Generating all subsets requires iterating through 2^n possibilities, as each element can either be present or absent in a subset. For each subset, we calculate the 'niceness' and check for validity. Checking validity involves iterating through the subset, which takes O(n) time in the worst case. However, the dominant factor is the generation of 2^n subsets, so the overall time complexity is O(2^n * n). Simplifying by removing the smaller factor, this remains exponential and represented as O(2^n).

Space Complexity

O(N) – The brute force approach described considers every possible combination of books. While calculating niceness and checking height constraints might use constant space, the critical space usage comes from generating these combinations. In the worst-case scenario, where we have N books, we might implicitly store a combination of books (e.g., using a boolean array of size N to indicate if a book is selected). Therefore, the auxiliary space is proportional to the number of books, N, resulting in a space complexity of O(N).

Optimal Solution

Approach

The best way to solve this problem is to build 'V' shaped arrangements of books. We find the peak height for each possible 'V' and then calculate the total number of books in that 'V'.

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

Go through the book counts, one at a time, to consider each as the potential highest point of a 'V' shape.
For each potential peak, expand to the left and right, building a 'V' shaped arrangement.
When adding books to the left or right, always choose the largest number you can, but only as many as will keep the counts increasing on the way up to the peak and decreasing on the way down.
Count the number of books used in this 'V' arrangement.
Keep track of the biggest 'V' arrangement you've found so far, along with the total books used in it.
After checking all possible peaks, the largest book count you recorded is the answer.

Code Implementation

def maximum_number_of_books_you_can_take(book_counts):
    maximum_books_taken = 0
    number_of_book_stacks = len(book_counts)

    for peak_index in range(number_of_book_stacks):
        peak_height = book_counts[peak_index]
        total_books_taken = peak_height
        left_count = peak_height - 1
        # Expand left from peak
        for left_index in range(peak_index - 1, -1, -1):
            if book_counts[left_index] < left_count:
                total_books_taken += book_counts[left_index]
                left_count = book_counts[left_index] - 1
            else:
                # Avoid decreasing book counts
                if left_count > 0:
                    total_books_taken += left_count
                    left_count -= 1
                else:
                    break
        right_count = peak_height - 1

        # Expand right from peak
        for right_index in range(peak_index + 1, number_of_book_stacks):
            if book_counts[right_index] < right_count:
                total_books_taken += book_counts[right_index]
                right_count = book_counts[right_index] - 1
            else:
                # Avoid decreasing book counts
                if right_count > 0:
                    total_books_taken += right_count
                    right_count -= 1
                else:
                    break

        # Update max books
        maximum_books_taken = max(maximum_books_taken, total_books_taken)

    return maximum_books_taken

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n book counts, considering each as a potential peak of a 'V' shape. For each potential peak, it expands left and right, potentially examining all books to the left and right of that peak to construct the 'V'. This nested process, where each of the n elements may trigger a walk across almost all other elements to form the 'V', results in approximately n * n/2 operations. Thus, the time complexity is O(n²).

Space Complexity

O(1) – The provided plain English explanation describes an iterative process that considers each element of the input (book counts) as a potential peak. It expands left and right to build a 'V' shape but does not mention storing these 'V' shapes explicitly. The algorithm only maintains the 'largest book count found so far' which requires constant space. Therefore, the algorithm uses a constant amount of auxiliary space, independent of the number of books (N), resulting in O(1) space complexity.

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately as no books can be taken from an empty collection.
Array with a single element	Return the value of that single element, as only that book can be taken.
All books have the same height	The solution should correctly calculate the number of books even if all heights are identical.
Heights are in strictly increasing order	The algorithm should still function correctly to maximize total height.
Heights are in strictly decreasing order	The algorithm should return the height of the first element.
Integer overflow if summing many large book heights	Use a data type capable of storing potentially large sums, like long.
Input array contains extremely large number of books	Ensure the chosen algorithm's time and space complexity remains reasonable for large inputs, avoiding quadratic or exponential behavior.
No books can be taken according to the problem constraint	The algorithm should correctly return 0 when no books meet the height constraint.

Null or empty input array

How to Handle:

Return 0 immediately as no books can be taken from an empty collection.

Array with a single element

How to Handle:

Return the value of that single element, as only that book can be taken.

All books have the same height

How to Handle:

The solution should correctly calculate the number of books even if all heights are identical.

Heights are in strictly increasing order

How to Handle:

The algorithm should still function correctly to maximize total height.

Heights are in strictly decreasing order

How to Handle:

The algorithm should return the height of the first element.

Integer overflow if summing many large book heights

How to Handle:

Use a data type capable of storing potentially large sums, like long.

Input array contains extremely large number of books

How to Handle:

Ensure the chosen algorithm's time and space complexity remains reasonable for large inputs, avoiding quadratic or exponential behavior.

No books can be taken according to the problem constraint

How to Handle:

The algorithm should correctly return 0 when no books meet the height constraint.