Find Books with No Available Copies solution and explanation
2 more videos on this problem
Leetcode 3570 - Learn SQL - Find Books with No Available Copies | Everyday Data ScienceEveryday Data Science · 8:43 · 681 views
Leetcode 3570 Find Books with No Available CopiesAlgorithmicIQ · 10:37 · 187 views
LeetCode 3570: Find Books with No Available Copies [SQL] | EasySaranya Devarapalli · 8:44 · 73 views
The problem
Table: library_books
+------------------+---------+ | Column Name | Type | +------------------+---------+ | book_id | int | | title | varchar | | author | varchar | | genre | varchar | | publication_year | int | | total_copies | int | +------------------+---------+ book_id is the unique identifier for this table. Each row contains information about a book in the library, including the total number of copies owned by the library.
Table: borrowing_records
+---------------+---------+ | Column Name | Type | +---------------+---------+ | record_id | int | | book_id | int | | borrower_name | varchar | | borrow_date | date | | return_date | date | +---------------+---------+ record_id is the unique identifier for this table. Each row represents a borrowing transaction and return_date is NULL if the book is currently borrowed and hasn't been returned yet.
Write a solution to find all books that are currently borrowed (not returned) and have zero copies available in the library.
- A book is considered currently borrowed if there exists a borrowing record with a NULL
return_date
Return the result table ordered by current borrowers in descending order, then by book title in ascending order.
The result format is in the following example.
Example:
Input:
library_books table:
+---------+------------------------+------------------+----------+------------------+--------------+ | book_id | title | author | genre | publication_year | total_copies | +---------+------------------------+------------------+----------+------------------+--------------+ | 1 | The Great Gatsby | F. Scott | Fiction | 1925 | 3 | | 2 | To Kill a Mockingbird | Harper Lee | Fiction | 1960 | 3 | | 3 | 1984 | George Orwell | Dystopian| 1949 | 1 | | 4 | Pride and Prejudice | Jane Austen | Romance | 1813 | 2 | | 5 | The Catcher in the Rye | J.D. Salinger | Fiction | 1951 | 1 | | 6 | Brave New World | Aldous Huxley | Dystopian| 1932 | 4 | +---------+------------------------+------------------+----------+------------------+--------------+
borrowing_records table:
+-----------+---------+---------------+-------------+-------------+ | record_id | book_id | borrower_name | borrow_date | return_date | +-----------+---------+---------------+-------------+-------------+ | 1 | 1 | Alice Smith | 2024-01-15 | NULL | | 2 | 1 | Bob Johnson | 2024-01-20 | NULL | | 3 | 2 | Carol White | 2024-01-10 | 2024-01-25 | | 4 | 3 | David Brown | 2024-02-01 | NULL | | 5 | 4 | Emma Wilson | 2024-01-05 | NULL | | 6 | 5 | Frank Davis | 2024-01-18 | 2024-02-10 | | 7 | 1 | Grace Miller | 2024-02-05 | NULL | | 8 | 6 | Henry Taylor | 2024-01-12 | NULL | | 9 | 2 | Ivan Clark | 2024-02-12 | NULL | | 10 | 2 | Jane Adams | 2024-02-15 | NULL | +-----------+---------+---------------+-------------+-------------+
Output:
+---------+------------------+---------------+-----------+------------------+-------------------+ | book_id | title | author | genre | publication_year | current_borrowers | +---------+------------------+---------------+-----------+------------------+-------------------+ | 1 | The Great Gatsby | F. Scott | Fiction | 1925 | 3 | | 3 | 1984 | George Orwell | Dystopian | 1949 | 1 | +---------+------------------+---------------+-----------+------------------+-------------------+
Explanation:
- The Great Gatsby (book_id = 1):
- Total copies: 3
- Currently borrowed by Alice Smith, Bob Johnson, and Grace Miller (3 borrowers)
- Available copies: 3 - 3 = 0
- Included because available_copies = 0
- 1984 (book_id = 3):
- Total copies: 1
- Currently borrowed by David Brown (1 borrower)
- Available copies: 1 - 1 = 0
- Included because available_copies = 0
- Books not included:
- To Kill a Mockingbird (book_id = 2): Total copies = 3, current borrowers = 2, available = 1
- Pride and Prejudice (book_id = 4): Total copies = 2, current borrowers = 1, available = 1
- The Catcher in the Rye (book_id = 5): Total copies = 1, current borrowers = 0, available = 1
- Brave New World (book_id = 6): Total copies = 4, current borrowers = 1, available = 3
- Result ordering:
- The Great Gatsby appears first with 3 current borrowers
- 1984 appears second with 1 current borrower
Output table is ordered by current_borrowers in descending order, then by book_title in ascending order.
Approach overview
Problem Overview: You have a books table with a total copy count per book and a borrowing table with one row per loan. A loan is active while its return date is NULL. Return every book where the number of active loans equals or exceeds its total copies, so no copy is available.
Approach 1: Correlated Subquery (O(n * m) time, O(1) extra space)
For each row in the books table, run a subquery that counts active loans for that book_id. Compare that count to total_copies and keep the row when the count is at least the total. The database re-runs the subquery once per book, so the cost scales with the number of books times the scan cost per lookup. This works on small tables and shows you understand the filter logic, but it does not scale when the borrowing table grows into millions of rows without an index on book_id.
Approach 2: Group Aggregation + Join (O(n + m) time, O(k) space)
Filter the borrowing table first with WHERE return_date IS NULL. Group those rows by book_id and count them. Join the grouped result to the books table on book_id, then keep rows where the active count is greater than or equal to total_copies. The engine scans the borrowing table once to build the groups, then does a single hash or merge join against the books table. Space is proportional to the number of distinct books with active loans, which is the k in the bound. This is the solution to use in production and in interviews. In Pandas, the same logic maps to groupby on the filtered loans, a merge with the books frame, and a boolean mask on the comparison.
Recommended for interviews: Start with the correlated subquery to show you can express the condition. Then move to group aggregation with a join to show you can reduce repeated work to one pass. Interviewers look for the IS NULL filter applied before the aggregation and a join that does not multiply rows. Watch for books with zero loans: they have no group row, so an inner join drops them, which is correct here because a book with no active loans always has copies available.
Related topics: database, join, aggregation.
Solution
Thinking
A book has no available copy when the number of open loans equals
total_copies. Count rows with a nullreturn_datebybook_idand inner-join the book table.Keep
current_borrowers = total_copies, sort by that count descending and title ascending, and project the requested columns.
First, we count the current number of borrowers for each book, then join this result with the book information table to filter out books where the current number of borrowers equals the total number of copies. Finally, we sort the results by the number of current borrowers in descending order, and if there is a tie, by book title in ascending order.
# Write your MySQL query statement below
WITH
T AS (
SELECT book_id, COUNT(1) current_borrowers
FROM borrowing_records
WHERE return_date IS NULL
GROUP BY 1
)
SELECT book_id, title, author, genre, publication_year, current_borrowers
FROM
library_books
JOIN T USING (book_id)
WHERE current_borrowers = total_copies
ORDER BY 6 DESC, 2;import pandas as pd
def find_books_with_no_available_copies(
library_books: pd.DataFrame, borrowing_records: pd.DataFrame
) -> pd.DataFrame:
current_borrowers = (
borrowing_records[borrowing_records["return_date"].isna()]
.groupby("book_id")
.size()
.rename("current_borrowers")
.reset_index()
)
merged = library_books.merge(current_borrowers, on="book_id", how="inner")
fully_borrowed = merged[merged["current_borrowers"] == merged["total_copies"]]
fully_borrowed = fully_borrowed.sort_values(
by=["current_borrowers", "title"], ascending=[False, True]
)
cols = [
"book_id",
"title",
"author",
"genre",
"publication_year",
"current_borrowers",
]
return fully_borrowed[cols].reset_index(drop=True)Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Correlated Subquery | O(n * m) | O(1) extra | Small tables, quick prototype, no index on book_id |
| Group Aggregation + Join | O(n + m) | O(k) for groups | General case, production queries, interviews |
Frequently asked questions
Is Find Books with No Available Copies easy or hard?
It is rated Easy with a roughly 56 percent acceptance rate. The difficulty comes from remembering to filter NULL return dates before grouping and from choosing an inner join that keeps only books matching the condition.
Find Books with No Available Copies Python/Java solution
In Python with Pandas, filter the loans where return_date is null, group by book_id and count, merge the result with the books DataFrame, and keep rows where the count is at least total_copies. The same logic applies in Java through a SQL query over JDBC, since the problem is solved as a database query rather than a procedural function.
How to solve Find Books with No Available Copies in O(n)?
Count active loans in one pass by grouping the borrowing table on book_id with the filter for NULL return dates. Then join the counts to the books table and compare each count to total_copies in the WHERE clause. Avoid correlated subqueries, since they repeat the loan scan for each book.
What is the best approach for Find Books with No Available Copies?
The best approach is group aggregation with a join. Filter the borrowing rows where the return date is NULL, group them by book_id to count active loans, then join that result to the books table and keep books where the count is at least total_copies. It scans each table once and runs in O(n + m) time.
Is Find Books with No Available Copies asked at Google/Amazon/Meta?
This problem is tagged as a database question on FleetCode, and it is a common style of SQL screening question at large tech companies. Interview loops at Amazon, Google, and Meta often include joins with aggregation and NULL filtering, which this problem tests directly.
What data structure is used in Find Books with No Available Copies?
The problem uses relational tables rather than a classic data structure. Internally, the database builds a hash table or sorts rows to group loans by book_id, then uses a hash or merge join to match each group with the books table.
What is the time complexity of Find Books with No Available Copies?
The optimal group aggregation solution runs in O(n + m) time, where n is the number of books and m is the number of borrowing records, since each table is read once and joined with a hash or merge join. The correlated subquery alternative runs in O(n * m) time because it re-scans loans for every book.