Data structures & algorithms (Beginner to Intermediate)

Free guided path13 chapters99+ problems

Earn badges and level up

Introduction

You must have witnessed the technological revolution if you were born between the late 1900s and the early 2000s. The transition from phones to smartphones or a loading icon to actual HD videos on YouTube is truly fascinating.

After seeing what has happened in the last two decades, I am optimistic about the future of computer science. Although we cannot predict what will happen shortly, one thing is certain: software developers will make a lot of money. So let's do our best to become one, and the key to landing an SDE job is to be a master of DSA problems.

So, without further ado, let's get this party started.

Ms Alice is a computer scientist with a large library. She recently purchased several new books and is now planning to construct a shelf for them.

Because her office is so tiny, the width of each shelf must be less than 'SHELF_WIDTH' for it to fit.

You are given an array of ‘BOOKS’ where BOOKS[i] = [HEIGHT_{i}, WIDTH_{i}] indicates the width and height of the book, ‘i’.

Some of the books are placed on the shelf so that their total width does not surpass 'SHELF_WIDTH.' If there are ‘N’ books on the shelf, and we have ‘X’ books on one level, and placing the (X + 1)th book on that level exceeds 'SHELF_WIDTH', we will keep it on the next level shelf. The height of each shelf is the maximum height of the books placed on it. We repeat the process unless there are no books left. The height of the shelf will be the summation of the height of each shelf.

Note that the order of the books we place at each step of the procedure is the same as the specified sequence of books.

For example, if there are four books, we can place the first and second books on level 1 and the third and fourth books on level 2.

After placing books in this manner, return the minimum possible height for the bookshelf.

Example

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Approach 1- Recursive

The brute force approach for the problem will be to try every possible arrangement of books and find the MINIMUM_HEIGHT. So for each book, we have two choices either to place it on the next shelf or to adjust it to the same current shelf.

The choice diagram for recursion would look something like this.

Let’s define the Function solver()parameters and how they would work.

Parameters

BOOKS - Vector of Books.

SHELF_WIDTH - Maximum shelf width.

INDEX - Index of the current book.

CURRENT_WIDTH - Width of all the books on a current shelf together.

SHELF_HEIGHT - Height of the current shelf.

HEIGHT - The total height of the shelf after placing the index book.

Algorithm

We’ll check if we have traversed all books, i.e., i == BOOKS.size(), then return ‘HEIGHT’.

Next, we add the width of ‘BOOK[INDEX]’ to the ‘CURRENT_WIDTH’.

If this width is less than equal to ‘SHELF_WIDTH’, we have two choices either to keep the book on the same shelf or the next shelf. So we've two function calls here and take the minimum of the two.

Else, we place the book on the next shelf. In this case, we make one function call.

At last, we return the answer.

Let’s try to code it now.

Program

#include <iostream>
#include <vector>
using namespace std;
// Function to try every possible arrangement of books to find the minimum height of the shelf.
int solver(vector<vector<int>> &books, int i, int currentWidth, int shelfHeight, int height, int shelfWidth)
{
// If we have placed all the books then return height.
if (i == books.size())
{
return height + shelfHeight;
}
// Add current book width to current shelf width.
int width = currentWidth + books[i][0];
int ans;
// If the resultant width is less than ‘SHELF_WIDTH’, we can either place this book on the same shelf or keep it in the next shelf.
if (width <= shelfWidth)
{
// Minimum height when the current book is kept on the same shelf.
int sameShelf = solver(books, i + 1, width, max(shelfHeight, books[i][1]), height, shelfWidth);
// Minimum height when the current book is kept on the next shelf.
int nextShelf = solver(books, i + 1, books[i][0], books[i][1], height + shelfHeight, shelfWidth);
// Next we see which will give us minimum height.
ans = min(sameShelf, nextShelf);
}
// If the resultant width exceeds ‘SHELF_WIDTH’, then we keep this book on the next shelf.
else
{
ans = solver(books, i + 1, books[i][0], books[i][1], height + shelfHeight, shelfWidth);
}
// Return minimum height.
return ans;
}
//Function that returns Minimum height of shelf needed to fit all N books.
int minHeightShelf(vector<vector<int>> &books, int shelfWidth)
{
// Call main solver Function.
return solver(books, 1, books[0][0], books[0][1], 0, shelfWidth);
}
int main()
{
int n;
cout << "Enter the number of books: ";
cin >> n;
int shelfWidth;
cout << "Enter the value of maximum shelf width: ";
cin >> shelfWidth;
cout << "Enter the Books width and height:\n";
vector<vector<int>> books(n, vector<int>(2));
for (int i = 0; i < n; i++)
{
cin >> books[i][0] >> books[i][1];
}
int ans = minHeightShelf(books, shelfWidth);
cout << "The minimum height of shelf needed to fit all books is: " << ans << endl;
return 0;
}

Input

Enter the number of books: 6
Enter the value of maximum shelf width: 5
Enter the Books width and height:
1 2
4 3
3 2
2 5
1 1
1 2

Output

The minimum height of the shelf needed to fit all the books is: 10

Time Complexity

O(2 ^ N), where ‘N’ is the number of books.

We have two choices for each book: we keep it on the next shelf or the same shelf. So roughly for each 'N' book, we will call the recursive function twice, resulting in exponential time complexity.

Space Complexity

O(N), where ‘N’ is the number of books.

Since at a particular time, there will be at max 'N' function calls in the stack.

Approach 2 - Dynamic Programming

The second approach to the problem is using Bottom-Up Dynamic programming.

To start, we'll place each book on the next shelf and then iterate over the previous 0 to i - 1 books and try to fit as many books as possible on the previous shelves.

As we are iterating i - 1(range 0 to N - 1) books back for each book, the time complexity will be O(N ^ 2) which is far better than exponential.

Let’s discuss the algorithm in detail now.

First, we initialize an array ‘DP’ of size 'N + 1’ where DP[i] will denote the minimum height of the shelf after placing i^{th }book.

We’ll set DP[0] = 0 and DP[1] = BOOK[0][1] (height of the first book).

Then we’ll loop from the second book till the last. And for each book we’ll first place it in the next shelf, i.e., DP[i] = DP[i - 1] + book[i][1] (height).

Next, we loop through the previous books and try to fit the current book.

In the end, we return DP[N].

Program

#include <iostream>
#include <vector>
using namespace std;
// Function that returns minimum height of shelf needed to fit all N books.
int minHeightShelves(vector<vector<int>> &books, int shelfWidth)
{
// Number of Books.
int n = books.size();
// If we have only one book to place then return the height of that book.
if (n == 1)
return books[0][1];
// Initialize a ‘DP’ table where DP[i] represents the minimum height of the shelf when there are 1 to i books to place.
int dp[n + 1];
// If there is no book to place answer = 0.
dp[0] = 0;
// If we have one book to place, the answer is the height of that book.
dp[1] = books[0][1];
int height, width;
// Now, we iterate from the second book up to the last one and compute the answer.
for (int i = 2; i <= n; i++)
{
height = books[i - 1][1];
width = books[i - 1][0];
// In the worst case, we'll place the next book on the next shelf and hence we'll simply add its height to the previous minimum height.
dp[i] = dp[i - 1] + height;
// We then try to adjust this book to the previous levels.
int j = i - 1;
while (j > 0 && width < shelfWidth)
{
width += books[j - 1][0];
// Check if the combined width does not exceeds SHELF_WIDTH.
if (width > shelfWidth)
break;
// Update the max height.
height = max(height, books[j - 1][1]);
// Next we update our dp value after adjusting the book at j-1 level.
dp[i] = min(dp[i], dp[j - 1] + height);
j--;
}
}
// Return DP[n].
return dp[n];
}
int main()
{
int n;
cout << "Enter the number of books: ";
cin >> n;
int shelfWidth;
cout << "Enter the value of maximum shelf width: ";
cin >> shelfWidth;
cout << "Enter the value of width and height for N books:\n ";
vector<vector<int>> books(n, vector<int>(2));
for (int i = 0; i < n; i++)
{
cin >> books[i][0] >> books[i][1];
}
int minHeight = minHeightShelves(books, shelfWidth);
cout << "The minimum height of shelf needed to fit all the books is: " << minHeight << endl;
return 0;
}

Input

Enter the number of books: 5
Enter the value of maximum shelf width: 5
Enter the Books width and height:
2 4
1 4
3 2
1 7
4 2

Output

The minimum height of the shelf needed to fit all the books is: 13

Time Complexity

O(N^2), where ‘N’ is the number of books.

Since for each ‘BOOK[i]’, we are iterating over all books from 0 to i - 1.

Working up a dynamic programming solution is always a challenge. But you can always figure out the DP solution once you have the idea of the problem and the recursive solution.

On the Coding Ninjas Platform, we have a variety of such problems and blogs. Additionally, Coding Ninjas recently introduced the Coding Ninjas Studio Test Series, a mainly developed test series for acing interviews.