# Filling Bookcase Shelves
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/filling-bookcase-shelves)
Canonical: https://scaleengineer.com/dsa/problems/filling-bookcase-shelves
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
**Companies:** [Flipkart](https://scaleengineer.com/companies/flipkart)
---
## Problem
You are given an array `books` where `books[i] = [thicknessi, heighti]` indicates the thickness and height of the `ith` 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:**

![](https://assets.glich.co/dsa/filling-bookcase-shelves/image0.png) 

**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 <= thicknessi <= shelfWidth <= 1000`
* `1 <= heighti <= 1000`

# Approaches
## Brute-force Recursion
This approach uses a straightforward recursive method to explore every possible valid arrangement of books on the shelves. It starts from the first book and, for each book, tries all possibilities of forming a shelf with the subsequent books. This exhaustive search guarantees finding the minimum height but at a very high computational cost.
**Time:** O(2^n), where n is the number of books. The number of ways to partition the books into shelves can be exponential, leading to an exponential number of recursive calls. · **Space:** O(n), where n is the number of books. This is due to the maximum depth of the recursion stack.
**Pros:** Simple to understand and implement as it directly models the problem's decision-making process.; Correctly solves the problem for very small inputs.
**Cons:** Extremely inefficient due to a large number of redundant calculations for the same subproblems.; Will result in a 'Time Limit Exceeded' error on most platforms for the given constraints.
### Explanation
We define a recursive function, say `solve(i)`, which calculates the minimum height required to place books from index `i` to the end of the array. The base case for the recursion is when `i` reaches the end of the books array, at which point we return 0 as no more books need to be placed.

In the recursive step, for the current book at index `i`, we iterate through the subsequent books (from `i` to `n-1`) to form a new shelf. For each potential shelf containing books from `i` to `j`, we first check if its total thickness is within the `shelfWidth`. If it is, we calculate the height of this shelf (which is the maximum height of any book on it) and add it to the result of the recursive call for the remaining books, i.e., `solve(j + 1)`. We keep track of the minimum total height found among all valid choices for the current shelf.

This method repeatedly solves the same subproblems. For example, `solve(5)` will be called from `solve(0)`, `solve(1)`, `solve(2)`, etc., leading to an exponential number of function calls.

```java
class Solution {
    public int minHeightShelves(int[][] books, int shelfWidth) {
        return solve(books, shelfWidth, 0);
    }

    private int solve(int[][] books, int shelfWidth, int i) {
        if (i == books.length) {
            return 0;
        }

        int minTotalHeight = Integer.MAX_VALUE;
        int currentShelfWidth = 0;
        int currentShelfHeight = 0;

        // Try placing books from i to j on the current shelf
        for (int j = i; j < books.length; j++) {
            int thickness = books[j][0];
            int height = books[j][1];

            currentShelfWidth += thickness;
            if (currentShelfWidth > shelfWidth) {
                break;
            }

            currentShelfHeight = Math.max(currentShelfHeight, height);
            int remainingHeight = solve(books, shelfWidth, j + 1);
            
            // We need to handle the case where remainingHeight is MAX_VALUE to avoid overflow
            if (remainingHeight != Integer.MAX_VALUE) {
                minTotalHeight = Math.min(minTotalHeight, currentShelfHeight + remainingHeight);
            }
        }

        return minTotalHeight;
    }
}
```
### Algorithm
- Define a recursive function `solve(i)` that computes the minimum height for placing books from index `i` to the end.
- **Base Case:** If `i` equals the total number of books `n`, it means all books are placed, so return 0.
- **Recursive Step:** For the current book `i`, we try to form a new shelf by including books from `i` to `j` (where `j` ranges from `i` to `n-1`).
  - Initialize `min_height` to infinity.
  - Start a loop for `j` from `i` to `n-1`.
  - In the loop, maintain the `current_shelf_width` and `current_shelf_height` for books from `i` to `j`.
  - If `current_shelf_width` exceeds `shelfWidth`, break the loop as no more books can be added to this shelf.
  - Otherwise, calculate the total height for this configuration: `current_shelf_height + solve(j + 1)`.
  - Update `min_height = min(min_height, current_shelf_height + solve(j + 1))`. 
- Return `min_height`.
- The initial call is `solve(0)`.

## Dynamic Programming (Bottom-Up)
This problem exhibits optimal substructure and overlapping subproblems, making it ideal for dynamic programming. We can build a solution iteratively (bottom-up) by calculating the minimum height for an increasing number of books. We use a DP array, `dp[i]`, to store the minimum height of the bookcase after placing the first `i` books. This avoids the redundant computations of the brute-force approach.
**Time:** O(n^2), where n is the number of books. We have a nested loop structure. The outer loop runs `n` times (for `i` from 1 to `n`), and the inner loop also runs up to `n` times (for `j` from `i` down to 1). · **Space:** O(n), where n is the number of books. We use a DP array of size `n+1` to store the intermediate results.
**Pros:** Efficient and guarantees finding the optimal solution.; Handles the given constraints (n <= 1000) effectively.; Avoids re-computation by storing intermediate results.
**Cons:** Requires O(n) extra space for the DP table.; The O(n^2) time complexity might be too slow for extremely large inputs, but it's efficient enough for the given constraints.
### Explanation
We define a DP array, `dp`, of size `n+1`, where `n` is the number of books. `dp[i]` will store the minimum possible height of the bookcase containing the first `i` books (from index 0 to `i-1`).

The base case is `dp[0] = 0`, as a bookcase with zero books has zero height. We then iterate from `i = 1` to `n` to compute each `dp[i]`.

To calculate `dp[i]`, we consider all possibilities for the last shelf. The last shelf must contain book `i-1`. It might also contain books `i-2`, `i-3`, and so on. We can iterate backwards from book `i-1` (let's say its index is `j-1`) and try to add it to the current last shelf. For each group of books `[j-1, ..., i-1]` that fits on a single shelf, we calculate the height of that shelf (which is the max height in that group) and add it to the minimum height of the bookcase containing books up to `j-2`, which is already stored in `dp[j-1]`. We take the minimum over all such valid groupings.

The transition formula is: `dp[i] = min(dp[j-1] + max_height_of_shelf(j-1, i-1))` for all `j` from `i` down to 1, such that the books from `j-1` to `i-1` fit on one shelf.

This approach can also be implemented using top-down recursion with memoization, which is conceptually equivalent and yields the same complexity.

```java
class Solution {
    public int minHeightShelves(int[][] books, int shelfWidth) {
        int n = books.length;
        // dp[i] will store the minimum height for the first i books.
        int[] dp = new int[n + 1];
        
        // Base case: 0 books require 0 height.
        dp[0] = 0;

        // Initialize other dp values to a large number.
        for (int i = 1; i <= n; i++) {
            dp[i] = Integer.MAX_VALUE;
        }

        // Iterate through each book to compute dp values.
        for (int i = 1; i <= n; i++) {
            int currentShelfWidth = 0;
            int currentShelfHeight = 0;
            
            // Iterate backwards to consider placing books on the last shelf.
            // j is the 1-based index of the book.
            for (int j = i; j > 0; j--) {
                int thickness = books[j - 1][0];
                int height = books[j - 1][1];
                
                currentShelfWidth += thickness;
                
                // If the shelf width is exceeded, we can't add more books from before.
                if (currentShelfWidth > shelfWidth) {
                    break;
                }
                
                // Update the height of the current shelf.
                currentShelfHeight = Math.max(currentShelfHeight, height);
                
                // Update dp[i] with the minimum height.
                // dp[j-1] is the min height for books before the current shelf.
                dp[i] = Math.min(dp[i], dp[j - 1] + currentShelfHeight);
            }
        }
        
        return dp[n];
    }
}
```
### Algorithm
- Let `n` be the number of books.
- Create a DP array `dp` of size `n + 1`. `dp[i]` will store the minimum height for the first `i` books.
- Initialize `dp[0] = 0` (0 books need 0 height) and all other `dp[i]` to a large value (infinity).
- Iterate `i` from 1 to `n`:
  - This loop computes `dp[i]`.
  - Initialize `current_shelf_width = 0` and `current_shelf_height = 0`.
  - Iterate `j` backwards from `i` down to 1:
    - The inner loop considers placing books from `j-1` to `i-1` on the last shelf.
    - Add the thickness of book `j-1` to `current_shelf_width`.
    - If `current_shelf_width` exceeds `shelfWidth`, break the inner loop.
    - Update `current_shelf_height = max(current_shelf_height, height of book j-1)`.
    - The total height for this arrangement is `dp[j-1]` (min height for books before this shelf) + `current_shelf_height`.
    - Update `dp[i] = min(dp[i], dp[j-1] + current_shelf_height)`.
- The final answer is `dp[n]`.

# Solutions
### CSharp

```csharp
public class Solution {
    public int MinHeightShelves(int[][] books, int shelfWidth) {
        int n = books.Length;
        int[] f = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            int w = books[i - 1][0], h = books[i - 1][1];
            f[i] = f[i - 1] + h;
            for (int j = i - 1; j > 0; --j) {
                w += books[j - 1][0];
                if (w > shelfWidth) {
                    break;
                }
                h = Math.Max(h, books[j - 1][1]);
                f[i] = Math.Min(f[i], f[j - 1] + h);
            }
        }
        return f[n];
    }
}
```

### Java

```java
class Solution { public int minHeightShelves ( int [][] books , int shelfWidth ) { int n = books . length ; int [] f = new int [ n + 1 ]; for ( int i = 1 ; i <= n ; ++ i ) { int w = books [ i - 1 ][ 0 ], h = books [ i - 1 ][ 1 ]; f [ i ] = f [ i - 1 ] + h ; for ( int j = i - 1 ; j > 0 ; -- j ) { w += books [ j - 1 ][ 0 ]; if ( w > shelfWidth ) { break ; } h = Math . max ( h , books [ j - 1 ][ 1 ]); f [ i ] = Math . min ( f [ i ], f [ j - 1 ] + h ); } } return f [ n ]; } }
```

### CPP

```cpp
class Solution { public: int minHeightShelves ( vector < vector < int >>& books , int shelfWidth ) { int n = books . size (); int f [ n + 1 ]; f [ 0 ] = 0 ; for ( int i = 1 ; i <= n ; ++ i ) { int w = books [ i - 1 ][ 0 ], h = books [ i - 1 ][ 1 ]; f [ i ] = f [ i - 1 ] + h ; for ( int j = i - 1 ; j > 0 ; -- j ) { w += books [ j - 1 ][ 0 ]; if ( w > shelfWidth ) { break ; } h = max ( h , books [ j - 1 ][ 1 ]); f [ i ] = min ( f [ i ], f [ j - 1 ] + h ); } } return f [ n ]; } };
```

### Python

```python
class Solution : def minHeightShelves ( self , books : List [ List [ int ]], shelfWidth : int ) -> int : n = len ( books ) f = [ 0 ] * ( n + 1 ) for i , ( w , h ) in enumerate ( books , 1 ): f [ i ] = f [ i - 1 ] + h for j in range ( i - 1 , 0 , - 1 ): w += books [ j - 1 ][ 0 ] if w > shelfWidth : break h = max ( h , books [ j - 1 ][ 1 ]) f [ i ] = min ( f [ i ], f [ j - 1 ] + h ) return f [ n ]
```