2355. Maximum Number of Books You Can Take
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.
Depth first search can be used to find whether two components in a graph are connected.
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
vat indexi, we pop from the stack while its top element is greater than or equal tov. This ensures that our stackstkis always in increasing order. - We then set
left[i]to the top of the stackstkif the stack is not empty; this represents the index of the previous smaller or equal element innums. If the stack is empty, it means there is no previous element in thenumsarray smaller or equal tonums[i], which implies that we can takebooks[i]books from shelfi. - Push the current index
ionto 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
cntof the maximum contiguous books that we can take from the current shelf, which is eitherbooks[i]or a truncated count ifjis not too far fromi. - 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 asv - cnt + 1. - A sum
s, which is the sum of the series fromutovcalculated 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.
A heap is a ...?
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 pushito the stack.stk = [0].i = 1,nums[i] = 4: The top of the stack is equal tonums[i]; no stack operation needed.stk = [0, 1].i = 2,nums[i] = 2: Pop1from the stack becausenums[2] < nums[1]. The stack top is now less thannums[i], so push2to the stack.stk = [0, 2].i = 3,nums[i] = 0: Continue popping until the stack is empty since all elements are larger or equal. Push3to the stack.stk = [3].i = 4,nums[i] = 2: No pops needed, push4to the stack.stk = [3, 4].i = 5,nums[i] = -3: Pop all elements since they are greater.stkends 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 shelfbooks[1].dp[1] = dp[0] + books[1]dp[1] = 4 + 5 = 9i = 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]] + cntdp[2] = 4 + 1 = 5i = 3:left[3] = -1, It means take all available booksbooks[3].dp[3] = books[3] = 3i = 4:left[4] = 3, Calculate books as sequence starting from 1.cnt = 1(Only one book can be taken)dp[4] = dp[left[4]] + cntdp[4] = 3 + 1 = 4i = 5:left[5] = -1, Take available booksbooks[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`
511import 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}
581using 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};
531// 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.
56Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.
Which of the following method should we use to solve this problem?
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 thenumsarray by modifying thebooksbased on their index and sets up theleftarray. It takesO(n)time wherenis the length of thebooks. -
The second loop (also the first
forloop encountered) constructs theleftarray, 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 inO(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 contributesO(n)time complexity. -
Within the third loop, calculating
min(v, i - j)and the arithmetic sum(u + v) * cnt // 2is done inO(1). -
The
maxfunction inside the loop is alsoO(1)for each comparison but happensntimes resulting inO(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
numslist takesO(n)space wherenis the length of the inputbookslist. -
The
leftlist is of sizen, again takingO(n)space. -
The stack
stkstores indices but at any time will not store more thannindices, hence contributingO(n)space. -
The
dplist is used to store accumulative results and takesO(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.
What's the output of running the following function using input 56?
1KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13 def dfs(path, res):
14 if len(path) == len(digits):
15 res.append(''.join(path))
16 return
17
18 next_number = digits[len(path)]
19 for letter in KEYBOARD[next_number]:
20 path.append(letter)
21 dfs(path, res)
22 path.pop()
23
24 res = []
25 dfs([], res)
26 return res
271private static final Map<Character, char[]> KEYBOARD = Map.of(
2 '2', "abc".toCharArray(),
3 '3', "def".toCharArray(),
4 '4', "ghi".toCharArray(),
5 '5', "jkl".toCharArray(),
6 '6', "mno".toCharArray(),
7 '7', "pqrs".toCharArray(),
8 '8', "tuv".toCharArray(),
9 '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13 List<String> res = new ArrayList<>();
14 dfs(new StringBuilder(), res, digits.toCharArray());
15 return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19 if (path.length() == digits.length) {
20 res.add(path.toString());
21 return;
22 }
23 char next_digit = digits[path.length()];
24 for (char letter : KEYBOARD.get(next_digit)) {
25 path.append(letter);
26 dfs(path, res, digits);
27 path.deleteCharAt(path.length() - 1);
28 }
29}
301const KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13 let res = [];
14 dfs(digits, [], res);
15 return res;
16}
17
18function dfs(digits, path, res) {
19 if (path.length === digits.length) {
20 res.push(path.join(''));
21 return;
22 }
23 let next_number = digits.charAt(path.length);
24 for (let letter of KEYBOARD[next_number]) {
25 path.push(letter);
26 dfs(digits, path, res);
27 path.pop();
28 }
29}
30Recommended Readings
Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Monotonic Stack Deque Intro If you'd prefer a video iframe width 560 height 315 src https www youtube com embed Dq_ObZwTY_Q title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe The word monotonic means a list or a
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.