2355. Maximum Number of Books You Can Take

HardStackArrayDynamic ProgrammingMonotonic Stack

Problem Description

In this problem, we are provided with an integer array called books, where each element books[i] represents the number of books on the ith shelf in a bookshelf. The shelves are indexed starting from 0.

The task is to take books from a continuous section of the shelf, where we start from shelf l and end at shelf r inclusive, such that 0 <= l <= r < n. However, while taking books from these shelves, we must adhere to a specific rule: from each shelf i within the section l <= i < r, we must take fewer books than from the shelf i+1. In other words, the number of books taken should strictly increase with each shelf as you move from left to right within the chosen section.

Our goal is to determine the maximum number of books we can take from the shelves while following this rule.

Intuition

To solve this problem, we need to find a way to take as many books as possible from each shelf, taking into account the increasing sequence constraint and without missing any of the shelves.

A simple greedy approach of just taking as many books as possible from each shelf won't work here because of the constraint that the number of books taken must strictly increase from one shelf to the next. Also, directly trying to find the maximum for each possible section for l to r can lead to a time-consuming solution, since there could many possible sections.

The solution involves dynamic programming, and the intuition for the solution comes from realizing that the maximum number of books we can take from a shelf i is influenced by the number of books available on shelf i as well as the restrictions applied by the shelves on its left (due to the strictly increasing order requirement).

We transform the problem into a smaller sub-problem by noting that the number of books that we can take from the shelf i is bounded by the difference between the number of books on that shelf and its index i (since the counts must increase). Use this transformed nums array to maintain this offset.

Next, we create a monotonically increasing stack stk that helps us quickly determine the leftmost shelf from which we can start taking books to satisfy the strictly increasing condition up to the current shelf. We iterate through each shelf, and update the left bounds accordingly.

Lastly, we apply dynamic programming (dp) to find the solution. The dp array keeps track of the maximum number of books we can take from the bookshelf ending at each index. For each shelf i, we calculate the maximum number of books we can take from this shelf and potentially the sequence of shelves to its left by using the left bounds and the dp of the previous shelf in the bounds. We keep track of the overall maximum as we calculate the dp for each shelf, which will be our final answer.

The code enforces the constraints by limiting the number of books we can take from each shelf i and ensures strictly increasing order by using the left bounds and the offsets in the nums array. It uses a key dynamic programming insight to build upon the results of smaller sections of shelves to find the answer for larger sections, ultimately leading to the maximum number of books we can take from any section of the bookshelf.

Learn more about Stack, Dynamic Programming and Monotonic Stack patterns.

Solution Approach

The solution approach uses dynamic programming, an array transformation, a monotonically increasing stack for efficient retrieval of data, and careful calculation of the boundaries for taking books.

Firstly, a transformed array nums is created from the original books array by subtracting the index from the book count for each shelf, i.e., nums[i] = books[i] - i. This transformation is important because it helps in efficiently enforcing the strictly increasing book count condition.

The next step is to find the left boundary for each shelf, at or beyond which we must start taking books to ensure the increasing sequence rule. This is accomplished by using a monotonically increasing stack stk. Iterating through the nums array:

For every element v at index i, we pop from the stack while its top element is greater than or equal to v. This ensures that our stack stk is always in increasing order.
We then set left[i] to the top of the stack stk if the stack is not empty; this represents the index of the previous smaller or equal element in nums. If the stack is empty, it means there is no previous element in the nums array smaller or equal to nums[i], which implies that we can take books[i] books from shelf i.
Push the current index i onto the stack.

Next begins the dynamic programming phase, where we initialize a dp array to store the maximum number of books that can be taken ending at each shelf index. dp[0] starts as books[0] because that's the maximum we can take from the first shelf.

As we go through each shelf i, with a variable j representing left[i], which is the left boundary index — we calculate:

The count cnt of the maximum contiguous books that we can take from the current shelf, which is either books[i] or a truncated count if j is not too far from i.
A series, u, representing the count from which we would have to start taking books from the current shelf to maintain the increasing sequence, which is calculated as v - cnt + 1.
A sum s, which is the sum of the series from u to v calculated as (u + v) * cnt // 2.

The dp[i] is then set to this sum s plus the dp of the previous boundary j if j is not -1.

As we compute dp[i] for each shelf, we keep track of the maximum sum ans found at any stage, which, once the iterations are complete, holds the answer to the problem — the maximum number of books that can be taken from the bookshelf.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Imagine we have a books array [4, 5, 4, 3, 6, 2], which represents the number of books on each respective shelf of a bookshelf.

Following the solution approach:

Step 1: Transform the Array
Create a transformed nums array by subtracting the index from the number of books on each shelf.
Original books array: [4, 5, 4, 3, 6, 2]
Transformed nums array: [4 - 0, 5 - 1, 4 - 2, 3 - 3, 6 - 4, 2 - 5]
Resulting nums array: [4, 4, 2, 0, 2, -3]

Step 2: Use a Stack to Define Left Boundaries
Start iterating through nums and use a stack stk to keep track of indices of a monotonically increasing series.

Iteration through nums:

i = 0, nums[i] = 4: Stack is empty, so push i to the stack. stk = [0].
i = 1, nums[i] = 4: The top of the stack is equal to nums[i]; no stack operation needed. stk = [0, 1].
i = 2, nums[i] = 2: Pop 1 from the stack because nums[2] < nums[1]. The stack top is now less than nums[i], so push 2 to the stack. stk = [0, 2].
i = 3, nums[i] = 0: Continue popping until the stack is empty since all elements are larger or equal. Push 3 to the stack. stk = [3].
i = 4, nums[i] = 2: No pops needed, push 4 to the stack. stk = [3, 4].
i = 5, nums[i] = -3: Pop all elements since they are greater. stk ends empty.

Left bounds array after iteration: left = [-1, 0, 0, -1, 3, -1] (If the stack is empty the left bound is -1)

Step 3: Dynamic Programming to Calculate Maximum Books
Initialize a dp array to store the maximum books we can take, starting with dp[0] as books[0] which is 4. Now iterate to calculate dp[i].

Let's process each shelf:

i = 1: left[1] = 0, Calculate available books from current shelf books[1]. dp[1] = dp[0] + books[1] dp[1] = 4 + 5 = 9
i = 2: left[2] = 0, Calculate books as sequence starting from 1 (since 2 books taken from shelf 0). cnt = 1 (Because taking 2 books would violate increasing condition) dp[2] = dp[left[2]] + cnt dp[2] = 4 + 1 = 5
i = 3: left[3] = -1, It means take all available books books[3]. dp[3] = books[3] = 3
i = 4: left[4] = 3, Calculate books as sequence starting from 1. cnt = 1 (Only one book can be taken) dp[4] = dp[left[4]] + cnt dp[4] = 3 + 1 = 4
i = 5: left[5] = -1, Take available books books[5]. dp[5] = books[5] = 2

The dp array after processing: [4, 9, 5, 3, 4, 2]

The maximum number of books that can be taken is the largest number in dp, which is 9 (which is the sum of books from shelf 0 to shelf 1).

So, following the approach outlined in the solution, we were able to find that the maximum number of books we can take while maintaining the strictly increasing condition is 9.

Solution Implementation

1from typing import List
2
3class Solution:
4    def maximumBooks(self, books: List[int]) -> int:
5        # Adjust the books count considering the position constraint
6        adjusted_books = [count - idx for idx, count in enumerate(books)]
7        n = len(adjusted_books)
8      
9        # Initialize the left limit for each book stack
10        left_limits = [-1] * n
11        stack = []
12      
13        # Compute left limits for each position based on the adjusted book counts
14        for idx, value in enumerate(adjusted_books):
15            while stack and adjusted_books[stack[-1]] >= value:
16                stack.pop()
17            if stack:
18                left_limits[idx] = stack[-1]
19            stack.append(idx)
20      
21        max_books = 0  # This will hold the maximum number of books that can be collected
22        dp = [0] * n   # Dynamic programming array to store the best solution up to the current index
23      
24        # Initialize the first position
25        dp[0] = books[0]
26      
27        # Calculate the maximum books for each position
28        for i, book_count in enumerate(books):
29            left_bound = left_limits[i]
30            # Determine the number of books that can be collected at position i
31            stack_height = min(book_count, i - left_bound)
32          
33            # Calculate the first book count
34            first_book = book_count - stack_height + 1
35          
36            # Calculate the sum of the arithmetic series
37            stack_books = (first_book + book_count) * stack_height // 2
38          
39            # If there is no left bound, do not add any previous book count, else add dp[left_bound]
40            dp[i] = stack_books if left_bound == -1 else stack_books + dp[left_bound]
41            # Update the maximum books if the current position has a better solution
42            max_books = max(max_books, dp[i])
43      
44        # Return the maximum number of books that can be collected
45        return max_books
46
47# Example usage:
48# sol = Solution()
49# max_collectable_books = sol.maximumBooks([1, 3, 3, 2, 1])
50# print(max_collectable_books)  # Output will vary depending on the input list `books`
51

1import java.util.Arrays;
2import java.util.ArrayDeque;
3import java.util.Deque;
4
5class Solution {
6  
7    public long maximumBooks(int[] books) {
8        int n = books.length;
9        int[] adjustedBooks = new int[n];
10      
11        // Adjust the book counts by subtracting the current index from the book count at each position
12        for (int i = 0; i < n; ++i) {
13            adjustedBooks[i] = books[i] - i;
14        }
15      
16        // Initialize an array to track the nearest smaller value to the left
17        int[] leftSmallerIndex = new int[n];
18        Arrays.fill(leftSmallerIndex, -1);
19      
20        // Monotonically decreasing stack to find the nearest smaller values
21        Deque<Integer> stack = new ArrayDeque<>();
22      
23        // Iterate through each adjusted book count to populate leftSmallerIndex
24        for (int i = 0; i < n; ++i) {
25            // Pop all elements that are greater than or equal to the current element
26            while (!stack.isEmpty() && adjustedBooks[stack.peek()] >= adjustedBooks[i]) {
27                stack.pop();
28            }
29            // If stack isn't empty, it means we found a smaller element to the left
30            if (!stack.isEmpty()) {
31                leftSmallerIndex[i] = stack.peek();
32            }
33            // Push the current index onto the stack
34            stack.push(i);
35        }
36      
37        long maxBooks = 0; // To store the maximum book count
38        long[] dp = new long[n]; // Dynamic programming array to store the maximum books at each position
39      
40        dp[0] = books[0]; // Base case: At position 0, max books equal to the book count at the 0th position
41      
42        // Iterate through each position to find the maximum number of books
43        for (int i = 0; i < n; ++i) {
44            int leftIndex = leftSmallerIndex[i];
45            int bookCount = books[i];
46            int count = Math.min(bookCount, i - leftIndex);
47            int startValue = bookCount - count + 1;
48            long sum = (long)(startValue + bookCount) * count / 2; // Calculate the sum of the arithmetic series
49          
50            dp[i] = sum + (leftIndex == -1 ? 0 : dp[leftIndex]); // Calculate dp value for the current position
51            maxBooks = Math.max(maxBooks, dp[i]); // Update maxBooks if current dp value is larger
52        }
53      
54        // Return the maximum books that can be obtained
55        return maxBooks;
56    }
57}
58

1using ll = long long; // Define a type alias for long long as 'll'.
2
3class Solution {
4public:
5    // Function to find the maximum number of books.
6    long long maximumBooks(vector<int>& books) {
7        int n = books.size(); // Store the number of elements in the books vector.
8        // Create a nums vector to store adjusted values taking book positions into account.
9        vector<int> adjustedBooks(n);
10        for (int i = 0; i < n; ++i) adjustedBooks[i] = books[i] - i;
11      
12        // Create a vector to store the index of the leftmost position where the sequence can start.
13        vector<int> leftIndex(n, -1);
14      
15        // Stack to keep track of indices while iterating to find viable starting points.
16        stack<int> indexStack;
17      
18        // Fill out the leftIndex vector.
19        for (int i = 0; i < n; ++i) {
20            // Pop elements from the stack if the current element is smaller.
21            while (!indexStack.empty() && adjustedBooks[indexStack.top()] >= adjustedBooks[i]) {
22                indexStack.pop();
23            }
24            if (!indexStack.empty()) {
25                leftIndex[i] = indexStack.top(); // Store the index of the left sequence start.
26            }
27            indexStack.push(i); // Push the current index onto the stack.
28        }
29      
30        // Create a dp vector to store the maximum number of books up to the current index.
31        vector<ll> dp(n);
32        dp[0] = books[0]; // The first position will always have the number of books at index 0.
33        ll maxBooks = 0; // Variable to store the maximum number of books collectable.
34      
35        // Iterate through the books array to calculate max books.
36        for (int i = 0; i < n; ++i) {
37            int height = books[i]; // Height for this position.
38            int leftBoundIndex = leftIndex[i];
39            // Calculate how many positions we can include in the sequence.
40            int sequenceLength = min(height, i - leftBoundIndex);
41            // Calculate the height at the beginning of the sequence.
42            int startHeight = height - sequenceLength + 1;
43            // Calculate the sum of sequence using arithmetic progression formula.
44            ll sequenceSum = 1ll * (startHeight + height) * sequenceLength / 2;
45            // Calculate the dp value, adding sequence sum to the previous dp value if this isn't the first stack.
46            dp[i] = sequenceSum + (leftBoundIndex == -1 ? 0 : dp[leftBoundIndex]);
47            // Update maxBooks if this position gives a better result.
48            maxBooks = max(maxBooks, dp[i]);
49        }
50        return maxBooks; // Return the maximum number of books collectable.
51    }
52};
53

1// Define a type alias for number to 'Long'.
2type Long = number; 
3
4// Function to find the maximum number of books.
5function maximumBooks(books: number[]): Long {
6    let n: number = books.length; // Store the number of elements in the books array.
7
8    // Create an adjustedBooks array to store adjusted values accounting for book positions.
9    let adjustedBooks: number[] = books.map((book, index) => book - index);
10  
11    // Array to store the index of the leftmost position from where the sequence can start.
12    let leftIndex: number[] = new Array(n).fill(-1);
13
14    // Stack to keep track of indices while iterating to find viable starting points.
15    let indexStack: number[] = [];
16
17    // Fill out the leftIndex array.
18    for (let i = 0; i < n; i++) {
19        // Pop elements from the stack if the current element is smaller.
20        while (indexStack.length > 0 && adjustedBooks[indexStack[indexStack.length - 1]] >= adjustedBooks[i]) {
21            indexStack.pop();
22        }
23        if (indexStack.length > 0) {
24            leftIndex[i] = indexStack[indexStack.length - 1]; // Store the index of the left sequence start.
25        }
26        indexStack.push(i); // Push the current index onto the stack.
27    }
28  
29    // Array to store the maximum number of books up to the current index.
30    let dp: Long[] = new Array(n).fill(0);
31    dp[0] = books[0]; // The first position will always have the number of books at index 0.
32    let maxBooks: Long = dp[0]; // Variable to store the maximum number of books collectible.
33  
34    // Iterate through the books array to calculate the max number of books.
35    for (let i = 1; i < n; i++) {
36        let height: number = books[i]; // Height for this position.
37        let leftBoundIndex: number = leftIndex[i];
38        // Calculate how many positions we can include in the sequence.
39        let sequenceLength: number = Math.min(height, i - leftBoundIndex);
40        // Calculate the height at the beginning of the sequence.
41        let startHeight: number = height - sequenceLength + 1;
42        // Calculate the sum of sequence using the arithmetic progression formula.
43        let sequenceSum: Long = ((startHeight + height) * sequenceLength) / 2 as Long;
44        // Calculate the dp value, adding sequence sum to the previous dp value if this isn't the first stack.
45        dp[i] = sequenceSum + (leftBoundIndex === -1 ? 0 : dp[leftBoundIndex]);
46        // Update maxBooks if this position gives a better result.
47        maxBooks = Math.max(maxBooks, dp[i]);
48    }
49  
50    return maxBooks; // Return the maximum number of books collectible.
51}
52
53// Example usage:
54// let result = maximumBooks([4, 5, 4, 3, 3]);
55// console.log(result); // Output the result.
56

Time and Space Complexity

The given Python code aims to solve a problem where we need to find the maximum number of books one can collect given certain conditions. Specifically, the books array represents the heights of stacks of books, and one can only collect books in non-decreasing stack height order from left to right with the constraint that the stack heights differ by at most 1.

Time Complexity

The time complexity of the code can be dissected as follows:

The first loop (for i, v in enumerate(nums):) initializes the nums array by modifying the books based on their index and sets up the left array. It takes O(n) time where n is the length of the books.
The second loop (also the first for loop encountered) constructs the left array, utilizing a monotonic stack to store indices of the previous smaller element. Each element is pushed and popped at most once, and hence, the loop overall runs in O(n) time.
The third loop (for i, v in enumerate(books):) calculates the maximum number of books that can be taken from each index if one starts taking books from this index. This also iterates over all the elements once and computes the sum in constant time using the arithmetic series sum formula. Hence, this loop also contributes O(n) time complexity.
Within the third loop, calculating min(v, i - j) and the arithmetic sum (u + v) * cnt // 2 is done in O(1).
The max function inside the loop is also O(1) for each comparison but happens n times resulting in O(n) time.

Combining these steps, since they all occur sequentially, the overall time complexity of the algorithm is O(n).

Space Complexity

The space complexity can be analyzed as follows:

The nums list takes O(n) space where n is the length of the input books list.
The left list is of size n, again taking O(n) space.
The stack stk stores indices but at any time will not store more than n indices, hence contributing O(n) space.
The dp list is used to store accumulative results and takes O(n) space.

The ans variable and other loop indices take constant O(1) space.

Considering all the variables used, the overall space complexity is O(n), where n is the size of the input books array.

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

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

Question 1 out of 10

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Pre-order traversal

Post-order traversal

In-order traversal

Level-order traversal

I don’t know