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 .
Examples#
Example 1:
1
2
3
4
5
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:
1
2
Input: books =[[ 1 , 3 ],[ 2 , 4 ],[ 3 , 2 ]], shelfWidth = 6
Output: 4
Solution#
Method 1 - Recursion#
Try to place maximum books on the current shelf and call for the next shelf and maintain the minimum answer after placing every book on current shelf and return the minimum answer.
Now this leads to following cases:
Base Case : When all books are placed (i == n
), return 0.
Recursive Case : Try placing books on the current shelf until the width exceeds shelfWidth
, and recursively call dfs
for the next book to find the total height required.
Here is the video explanation:
VIDEO
Code#
Cpp
Java
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <vector>
#include <limits>
using namespace std;
class Solution {
public :
int minHeightShelves(vector< vector< int >>& books, int shelfWidth) {
return dfs (books, shelfWidth, 0 );
}
private :
int dfs(const vector< vector< int >>& books, int shelfWidth, int i) {
int n = books.size();
if (i == n) return 0 ;
int width = 0 ;
int height = 0 ;
int minHeight = numeric_limits< int >:: max();
for (int j = i; j < n; ++ j) {
width += books[j][0 ];
if (width > shelfWidth) break ;
height = max(height, books[j][1 ]);
minHeight = min(minHeight, height + dfs(books, shelfWidth, j + 1 ));
}
return minHeight;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public int minHeightShelves (int [][] books, int shelfWidth) {
return dfs(books, shelfWidth, 0);
}
private int dfs (int [][] books, int shelfWidth, int i) {
if (i == books.length ) {
return 0;
}
int width = 0;
int height = 0;
int minHeight = Integer.MAX_VALUE ;
for (int j = i; j < books.length ; j++ ) {
width += books[ j][ 0] ;
if (width > shelfWidth) {
break ;
}
height = Math.max (height, books[ j][ 1] );
minHeight = Math.min (minHeight, height + dfs(books, shelfWidth, j + 1));
}
return minHeight;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution :
def minHeightShelves (self, books: List[List[int]], shelfWidth: int) -> int:
n = len(books)
def dfs (i: int) -> int:
if i == n:
return 0
width = 0
height = 0
min_height = 10 ** 18
for j in range(i, n):
width += books[j][0 ]
if width > shelfWidth:
break
height = max(height, books[j][1 ])
min_height = min(min_height, height + dfs(j + 1 ))
return min_height
return dfs(0 )
Complexity#
⏰ Time complexity: O(2^n)
for exploring each subsets of books
🧺 Space complexity: O(n)
for using recursion stack
Dry Run#
Method 2 - Top Down DP#
Recursion might result in overlapping subproblems. We can store results of subproblems to avoid redundant calculations, thus optimizing the recursive solution with memoization.
Code#
Cpp
Java
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <vector>
#include <unordered_map>
#include <limits>
using namespace std;
class Solution {
public :
int minHeightShelves(vector< vector< int >>& books, int shelfWidth) {
memo.clear();
this -> books = books;
this -> shelfWidth = shelfWidth;
return dfs (0 );
}
private :
unordered_map< int ,int > memo;
vector< vector< int >> books;
int shelfWidth;
int dfs (int i) {
int n = books.size();
if (i == n) return 0 ;
if (memo.count(i)) return memo[i];
int width = 0 ;
int height = 0 ;
int minHeight = numeric_limits< int >:: max();
for (int j = i; j < n; ++ j) {
width += books[j][0 ];
if (width > shelfWidth) break ;
height = max(height, books[j][1 ]);
minHeight = min(minHeight, height + dfs(j + 1 ));
}
memo[i] = minHeight;
return minHeight;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
private Map< Integer, Integer> memo;
public int minHeightShelves (int [][] books, int shelfWidth) {
memo = new HashMap<> ();
return dfs(books, shelfWidth, 0);
}
private int dfs (int [][] books, int shelfWidth, int i) {
if (i == books.length ) {
return 0;
}
if (memo.containsKey (i)) {
return memo.get (i);
}
int width = 0;
int height = 0;
int minHeight = Integer.MAX_VALUE ;
for (int j = i; j < books.length ; j++ ) {
width += books[ j][ 0] ;
if (width > shelfWidth) {
break ;
}
height = Math.max (height, books[ j][ 1] );
minHeight = Math.min (minHeight, height + dfs(books, shelfWidth, j + 1));
}
memo.put (i, minHeight);
return minHeight;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution :
def minHeightShelves (self, books: List[List[int]], shelfWidth: int) -> int:
n = len(books)
memo = {}
def dfs (i: int) -> int:
if i == n:
return 0
if i in memo:
return memo[i]
width = 0
height = 0
min_height = 10 ** 18
for j in range(i, n):
width += books[j][0 ]
if width > shelfWidth:
break
height = max(height, books[j][1 ])
min_height = min(min_height, height + dfs(j + 1 ))
memo[i] = min_height
return min_height
return dfs(0 )
Complexity#
⏰ Time complexity: O(n^2)
🧺 Space complexity: O(n)
for using recursion stack
Method 3 - Bottom up DP#
Here are the points for bottom up DP:
DP Array Initialization : dp
array where dp[i]
represents the minimum height needed to place the first i
books.
Iterate Over Books : For each book, try placing it on the current shelf or start a new shelf, and update dp
array accordingly.
Result : Return dp[n]
, representing the minimum height for placing all n
books.
Code#
Cpp
Java
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <vector>
#include <limits>
using namespace std;
class Solution {
public :
int minHeightShelves(vector< vector< int >>& books, int shelfWidth) {
int n = books.size();
vector< int > dp(n+ 1 , 0 );
dp[0 ] = 0 ;
for (int i = 1 ; i <= n; ++ i) {
int width = 0 ;
int height = 0 ;
dp[i] = numeric_limits< int >:: max();
for (int j = i - 1 ; j >= 0 ; -- j) {
width += books[j][0 ];
if (width > shelfWidth) break ;
height = max(height, books[j][1 ]);
dp[i] = min(dp[i], dp[j] + height);
}
}
return dp[n];
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public int minHeightShelves (int [][] books, int shelfWidth) {
int n = books.length ;
int [] dp = new int [ n + 1] ;
dp[ 0] = 0;
for (int i = 1; i <= n; i++ ) {
int width = 0;
int height = 0;
dp[ i] = Integer.MAX_VALUE ;
for (int j = i - 1; j >= 0; j-- ) {
width += books[ j][ 0] ;
if (width > shelfWidth) {
break ;
}
height = Math.max (height, books[ j][ 1] );
dp[ i] = Math.min (dp[ i] , dp[ j] + height);
}
}
return dp[ n] ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution :
def minHeightShelves (self, books: List[List[int]], shelfWidth: int) -> int:
n = len(books)
dp = [0 ] * (n + 1 )
for i in range(1 , n + 1 ):
width = 0
height = 0
dp[i] = 10 ** 18
for j in range(i- 1 , - 1 , - 1 ):
width += books[j][0 ]
if width > shelfWidth:
break
height = max(height, books[j][1 ])
dp[i] = min(dp[i], dp[j] + height)
return dp[n]
Complexity#
⏰ Time complexity: O(n^2)
🧺 Space complexity: O(n)
for using dp[]
array