What is the time complexity of Filling Bookcase Shelves?

The optimal solution has a time complexity of O(n^2).

What data structures are used to solve Filling Bookcase Shelves?

This problem uses Array, Dynamic Programming. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Filling Bookcase Shelves?

Insight 1: Dynamic Programming is suitable for this problem because we need to find the optimal (minimum) height among many possible shelf arrangements. We can break down the problem into smaller subproblems: finding the minimum height for the first `i` books. Insight 2: The order of books is fixed, simplifying the problem. We only need to decide where to start a new shelf.

Which companies ask LeetCode 1105. Filling Bookcase Shelves in interviews?

This problem is frequently asked at Flipkart.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Filling Bookcase Shelves - LeetCode 1105 Solution

Filling Bookcase Shelves - Complete Solution Guide

Filling Bookcase Shelves is LeetCode problem 1105, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

You are given an array books where books[i] = [thickness i , height i ] indicates the thickness and height of the i th 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

Detailed Explanation

The problem asks us to arrange a given list of books onto shelves of a bookcase, where each shelf has a specified width. The goal is to minimize the total height of the bookcase. We must place the books in the order they appear in the input list. We can place as many books as possible on a shelf, as long as the sum of their thicknesses does not exceed the shelf width. The height of a shelf is determined by the tallest book placed on that shelf. The total bookcase height is the sum of the heights of each shelf. The input is a list of `books`, where each book is represented by its thickness and height, and an integer `shelfWidth`. The output is the minimum possible height of the bookcase.

Solution Approach

The provided code uses dynamic programming to solve this problem. It initializes a `dp` array where `dp[i]` stores the minimum height of the bookcase after placing the first `i` books. The code iterates through the books, and for each book `i`, it considers all possible starting points `j` for the last shelf (from `i-1` down to `0`). For each possible shelf starting point `j`, it calculates the width and maximum height of that shelf. If the shelf width is valid, it updates `dp[i]` with the minimum value between its current value and `dp[j] + max_height_on_shelf`. The final result is stored in `dp[n]`, which represents the minimum height after placing all `n` books.

Step-by-Step Algorithm

Step 1: Initialize a `dp` array of size `n+1` with infinity, where `n` is the number of books. `dp[0]` is initialized to 0, representing the base case (no books, no height).
Step 2: Iterate through the books from `i = 1` to `n` (inclusive). This represents placing the i-th book (books[i-1]).
Step 3: For each book `i`, iterate backward from `j = i-1` down to `0`. This represents considering all possible starting points for the last shelf. The last shelf starts from books[j].
Step 4: Calculate the current shelf width and maximum height on the shelf. Add the thickness of the current book `books[j]` to the `current_shelf_width` and update the `max_height_on_shelf` if necessary.
Step 5: Check if the `current_shelf_width` exceeds the `shelfWidth`. If it does, break the inner loop, since adding more books to this shelf is not feasible.
Step 6: If `dp[j]` is not infinity, update `dp[i]` with the minimum value between its current value and `dp[j] + max_height_on_shelf`. This represents the minimum height to shelve the first `i` books, considering the optimal height for the first `j` books plus the height of the current shelf.
Step 7: After iterating through all possible starting points for each book `i`, `dp[i]` will store the minimum height needed to shelve the first `i` books.
Step 8: Finally, return `dp[n]`, which contains the minimum height needed to shelve all `n` books.

Key Insights

Insight 1: Dynamic Programming is suitable for this problem because we need to find the optimal (minimum) height among many possible shelf arrangements. We can break down the problem into smaller subproblems: finding the minimum height for the first `i` books.
Insight 2: The order of books is fixed, simplifying the problem. We only need to decide where to start a new shelf.
Insight 3: We need to iterate backward from the current book to consider all possible combinations of books on the current shelf. This involves calculating the current shelf's width and height based on the books placed on it.
Insight 4: The `dp` array stores the minimum height for the first `i` books. `dp[i]` represents the minimum height needed to shelve the first `i` books.

Complexity Analysis

Time Complexity: O(n^2)

Space Complexity: O(n)

Topics

This problem involves: Array, Dynamic Programming.

Companies

Asked at: Flipkart.

Filling Bookcase Shelves | LeetCode 1105

Medium

Array Dynamic Programming

Time: O(n^2)Space: O(n)

Solution Code

Available in:

class Solution {
    public int minHeightShelves(int[][] books, int shelfWidth) {
        int n = books.length;
        int[] dp = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        dp[0] = 0;

        for (int i = 1; i <= n; i++) {
            int current_shelf_width = 0;
            int max_height_on_shelf = 0;

            for (int j = i - 1; j >= 0; j--) {
                int thickness = books[j][0];
                int height = books[j][1];
                current_shelf_width += thickness;

                if (current_shelf_width > shelfWidth) {
                    break;
                }

                max_height_on_shelf = Math.max(max_height_on_shelf, height);

                if (dp[j] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], dp[j] + max_height_on_shelf);
                }
            }
        }

        return dp[n];
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 1105: Filling Bookcase Shelves - Detailed explanation and solution approaches.

Topics

Array Dynamic Programming

Companies

Flipkart

Stats

Difficulty:Medium

Languages:4

Companies:1

Problem #:1105

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

8 steps

1
Step 1: Initialize a `dp` array of size `n+1` with infinity, where `n` is the number of books. `dp[0]` is initialized to 0, representing the base case (no books, no height).
2
Step 2: Iterate through the books from `i = 1` to `n` (inclusive). This represents placing the i-th book (books[i-1]).
3
Step 3: For each book `i`, iterate backward from `j = i-1` down to `0`. This represents considering all possible starting points for the last shelf. The last shelf starts from books[j].
4
Step 4: Calculate the current shelf width and maximum height on the shelf. Add the thickness of the current book `books[j]` to the `current_shelf_width` and update the `max_height_on_shelf` if necessary.
5
Step 5: Check if the `current_shelf_width` exceeds the `shelfWidth`. If it does, break the inner loop, since adding more books to this shelf is not feasible.
6
Step 6: If `dp[j]` is not infinity, update `dp[i]` with the minimum value between its current value and `dp[j] + max_height_on_shelf`. This represents the minimum height to shelve the first `i` books, considering the optimal height for the first `j` books plus the height of the current shelf.
7
Step 7: After iterating through all possible starting points for each book `i`, `dp[i]` will store the minimum height needed to shelve the first `i` books.
8
Step 8: Finally, return `dp[n]`, which contains the minimum height needed to shelve all `n` books.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n^2)

🐢 Quadratic - Gets slow with large inputs. Consider optimization!

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The time complexity is O(n^2) because of the nested loops. The outer loop iterates `n` times, and the inner loop iterates up to `n` times in the worst case. The space complexity is O(n) because the `dp` array has a size of `n + 1`.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Recursion with Memoization

A recursive approach can also be used with memoization to avoid recomputing the same subproblems. The recursion explores the possible shelf divisions and memoizes the results.

Time: O(n^2)Space: O(n^2) in the worst case due to recursion stack and memoization table, but can be O(n) if implemented carefully to discard unnecessary memoized results

Trade-offs: Recursion can be more intuitive for some, but can be less efficient due to function call overhead and potentially higher space complexity if memoization is not managed optimally. The iterative DP approach is usually preferred for its better space efficiency.

✨

Key Insights

1Insight 1: Dynamic Programming is suitable for this problem because we need to find the optimal (minimum) height among many possible shelf arrangements. We can break down the problem into smaller subproblems: finding the minimum height for the first `i` books.
2Insight 2: The order of books is fixed, simplifying the problem. We only need to decide where to start a new shelf.
3Insight 3: We need to iterate backward from the current book to consider all possible combinations of books on the current shelf. This involves calculating the current shelf's width and height based on the books placed on it.
4Insight 4: The `dp` array stores the minimum height for the first `i` books. `dp[i]` represents the minimum height needed to shelve the first `i` books.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Dynamic Programming

Breaking complex problems into smaller subproblems and storing results.

Edge Cases

Edge case 1: `books` is empty. The code handles this correctly since the outer loop will not execute and it will return `dp[0]`, which is initialized to 0.
Edge case 2: `shelfWidth` is small such that only one book can fit on each shelf. The algorithm correctly considers placing each book on its own shelf and finds the minimum total height.
Edge case 3: All books can fit on one shelf. The algorithm considers this case and calculates the total height by considering only one shelf, resulting in the height of the tallest book.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting to initialize `dp[0]` to 0. This is crucial because it represents the base case where no books are placed.

✗Common mistake 2: Not considering all possible starting points `j` for the last shelf. The inner loop should iterate from `i-1` down to `0` to explore all valid shelf arrangements.

✗Common mistake 3: Incorrectly calculating the shelf width or maximum shelf height. Ensure that you accumulate the thickness and find the maximum height correctly within the inner loop.

✗Common mistake 4: Not handling `Integer.MAX_VALUE` or `float('inf')` correctly, which can lead to overflow or incorrect comparisons. Always check if a `dp[j]` is not infinity before using it in the `min` calculation.

✗Common mistake 5: Failing to break the inner loop when `current_shelf_width` exceeds `shelfWidth`, leading to incorrect calculations and potentially wrong results. The loop must terminate when a shelf becomes too wide.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Optimizing the arrangement of items in a warehouse to minimize the vertical space used.

🏦Real-world scenario 2: Determining the optimal way to pack boxes of different sizes into a container to minimize the container's height.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

If stuck, try working through a small example by hand. The pattern often reveals itself.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

👨‍💻 From Experience

This problem pattern appears frequently in real codebases. I've used similar logic when building production systems.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: June 26, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 13

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 6

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJun 29

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

Should I use top-down (memoization) or bottom-up (tabulation)?

Start with top-down (recursion + memoization) as it directly maps to the recursive thinking and handles only needed subproblems. Convert to bottom-up for better space efficiency and to avoid stack overflow. Bottom-up is often faster due to no recursion overhead.

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Filling Bookcase Shelves"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether dynamic programming techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?