Is Maximum Number of Books You Can Take easy or hard?

LeetCode classifies this problem as Hard because it combines multiple concepts: monotonic stack boundaries, arithmetic sequence sums, and dynamic programming. Recognizing the books[i] - i transformation and maintaining the stack efficiently is the main challenge.

Maximum Number of Books You Can Take Python/Java solution

Most implementations use a monotonic stack and DP array. Python, Java, C++, and Go versions follow the same structure: iterate through shelves, maintain the stack condition, compute the valid segment length, and calculate the arithmetic progression sum for the decreasing sequence.

How to solve Maximum Number of Books You Can Take in O(n)?

Traverse the array while maintaining a monotonic stack of indices based on the transformed value books[i] - i. The stack helps find the farthest valid starting shelf for the decreasing sequence. Use dynamic programming to accumulate the sum of the arithmetic sequence for each valid segment ending at index i.

What is the best approach for Maximum Number of Books You Can Take?

The best approach uses a monotonic stack combined with dynamic programming. The stack identifies the nearest left boundary where the decreasing pattern breaks, while DP stores the maximum books for segments ending at each index. This reduces the problem to O(n) time and O(n) space.

Is Maximum Number of Books You Can Take asked at Google/Amazon/Meta?

Problems involving monotonic stacks and dynamic programming patterns appear frequently in interviews at companies like Google, Amazon, and Meta. Variants of range constraints, decreasing sequences, and stack-based boundary detection are common in senior-level algorithm rounds.

What data structure is used in Maximum Number of Books You Can Take?

The core data structure is a monotonic stack that maintains candidate shelf indices while preserving a specific ordering condition. Dynamic programming is used alongside it to accumulate maximum sums for valid segments. The input itself is processed as an array.

What is the time complexity of Maximum Number of Books You Can Take?

The optimal solution runs in O(n) time because each index is pushed and popped from the monotonic stack at most once. Dynamic programming stores partial results so segment sums are not recomputed. Space complexity is O(n) for the stack and DP array.

Description Hints 4 Solution Video 18:59

2355. Maximum Number of Books You Can Take

Hard40.9% acceptance1 companyPremium elsewhere, free here

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 of a bookshelf.

You are going to take books from a contiguous section of the bookshelf spanning from l to r where 0 <= l <= r < n. For each index i in the range l <= i < r, you must take strictly fewer books from shelf i than shelf i + 1.

Return the maximum number of books you can take from the bookshelf.

Example 1:

Input: books = [8,5,2,7,9]
Output: 19
Explanation:
- Take 1 book from shelf 1.
- Take 2 books from shelf 2.
- Take 7 books from shelf 3.
- Take 9 books from shelf 4.
You have taken 19 books, so return 19.
It can be proven that 19 is the maximum number of books you can take.

Example 2:

Input: books = [7,0,3,4,5]
Output: 12
Explanation:
- Take 3 books from shelf 2.
- Take 4 books from shelf 3.
- Take 5 books from shelf 4.
You have taken 12 books so return 12.
It can be proven that 12 is the maximum number of books you can take.

Example 3:

Input: books = [8,2,3,7,3,4,0,1,4,3]
Output: 13
Explanation:
- Take 1 book from shelf 0.
- Take 2 books from shelf 1.
- Take 3 books from shelf 2.
- Take 7 books from shelf 3.
You have taken 13 books so return 13.
It can be proven that 13 is the maximum number of books you can take.

Constraints:

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

Asked at 1 company

Amazon

Topics

Hints open one at a time

Hint 1

Create a dp array where dp[i] is the maximum number of books you can take if you can only take books from bookshelves 0 to i and you must take books from bookshelf i.

Hint 2

Keep taking as many books as you can (i.e. starting from bookshelf i and going backwards, you take arr[i], arr[i] - 1, arr[i] - 2, … books).

Hint 3

You may reach an index j where arr[j] < arr[i] - (i - j). Have we already found the maximum number of books you can take from bookshelves 0 to j? How do we quickly find such an index j?

Hint 4

Keep a stack of possible indices for j. If x is the number at the top of the stack, keep popping from the stack while arr[x] ≥ arr[i] - (i - x). This is because if the inequality mentioned before is true, x will never be an index j as index i will run out of items first.

18:59

Still stuck?Read the written solution, or watch a walkthrough.

Open solution