LeetCode Problem 3570

Difficulty: 🟢 Easy
Topics: Database

Solution

Problem Understanding

This problem asks us to identify books in a library system that are both fully unavailable for borrowing and currently have active borrowers who have not returned them yet.

We are given two tables. The library_books table contains static information about each book, including how many total physical copies exist in the library. The borrowing_records table captures individual borrow transactions, and a record is considered active if its return_date is NULL, meaning the book has not yet been returned.

The task is to compute, for each book, how many active borrowers it currently has, compare that against the total number of copies, and select only those books where the number of active borrowers is equal to the total number of copies. This condition ensures that there are zero available copies remaining in the library.

The output must include full book metadata along with a computed field current_borrowers, and it must be sorted first by current_borrowers in descending order, then by title in ascending order.

From a constraints perspective, this is a classic SQL aggregation and join problem. Even though constraints are not explicitly provided, typical LeetCode SQL problems imply potentially large datasets, so the solution should be linearithmic or linear in practice, relying on indexed grouping operations.

Key edge cases include books with no borrowing records, books where all borrowings are returned, books where active borrowings exceed total copies due to data inconsistencies, and books with exactly matching active borrow counts and total copies.

Approaches

The brute-force approach conceptually evaluates each book independently. For every book, we scan the entire borrowing_records table to count how many active (NULL return_date) records exist for that book. Then we compare this count to total_copies. While this is logically straightforward, it is inefficient because it repeatedly scans the same table for each book, leading to quadratic behavior.

The optimal approach uses aggregation. We first filter borrowing records to only active ones, group them by book_id, and compute counts in a single pass. Then we join this aggregated result with the library_books table. This reduces repeated scanning and leverages database indexing and grouping optimizations.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(B × R)	O(1)	For each book B, scan all borrowing records R
Optimal (Aggregation + Join)	O(B + R)	O(B)	Single scan with grouping and join

Algorithm Walkthrough

1. We begin by filtering the borrowing_records table to include only rows where return_date IS NULL. This step isolates currently active borrows, since returned books do not contribute to current unavailability.
2. Next, we group the filtered borrowing records by book_id. This allows us to compute how many active borrowers exist per book in a single aggregated pass rather than repeatedly scanning the dataset.
3. For each group, we compute COUNT(*) to obtain the number of active borrowers per book. This result is stored as a derived dataset, often referred to as a common table expression or subquery.
4. We then perform a LEFT JOIN between library_books and the aggregated borrowing counts on book_id. This ensures that every book is considered, even those without active borrowers.
5. For books that do not appear in the aggregated borrowing table, we treat their active borrower count as zero using COALESCE.
6. We compute the condition current_borrowers = total_copies to identify books with no available copies.
7. Finally, we sort the result first by current_borrowers in descending order and then by title in ascending order to satisfy the required output ordering.

Why it works: the grouping step ensures each book’s active borrow count is computed exactly once, and the join aligns this derived metric with the book metadata. The equality condition precisely captures the "no available copies" invariant. This problem asks us to determine which books in a library are completely borrowed, meaning all their copies are currently checked out. We are provided with two tables: library_books, which lists every book and the total number of copies the library owns, and borrowing_records, which records all borrowing events, with return_date indicating if a book has been returned or not.

We need to return books for which the number of current borrowers (borrowed books not yet returned, indicated by return_date IS NULL) equals the total number of copies owned. Additionally, the output must include the count of current borrowers and be sorted first by descending current borrower count, then by ascending book title.

Important points are that multiple borrowers can have the same book, a book may not be borrowed at all, and the borrow count may not exceed total copies (though logically it could if the data is inconsistent). The edge cases to consider include books with zero total copies, no borrowing records, or multiple borrowers for a single-copy book.

Approaches

A brute-force approach would involve iterating over each book in library_books, counting the current borrowings by scanning the borrowing_records table, and then comparing it to total_copies. This approach works correctly but can be inefficient because it may require scanning all borrowing records for each book, resulting in a potentially O(n * m) time complexity, where n is the number of books and m is the number of borrow records.

The optimal approach leverages SQL aggregation and joins. The key insight is that we do not need to iterate manually for each book. We can filter borrowing records for those that are currently borrowed (return_date IS NULL), group them by book_id, and count borrowers. Then, we join this aggregated result with library_books and filter for cases where the count equals the total copies. This reduces unnecessary scanning and leverages database engine optimizations.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * m)	O(1)	Iterate over books, count borrowers per book, compare to total copies
Optimal	O(m + n)	O(n)	Aggregate current borrowers per book, join with books, filter by total copies

Algorithm Walkthrough

1. Start by filtering the borrowing_records table to include only rows where return_date is NULL. This gives all current borrowings.
2. Group the filtered records by book_id and count the number of borrowers for each book. This produces a mapping of book_id → current_borrowers.
3. Join this aggregated table with library_books on book_id to bring in the book details and total copies.
4. Apply a filter where current_borrowers equals total_copies. This ensures only books with zero available copies are included.
5. Select the necessary columns: book_id, title, author, genre, publication_year, and current_borrowers.
6. Order the results first by current_borrowers descending and then by title ascending.

Why it works: By counting only active borrowings and comparing against the total copies, the algorithm guarantees that we capture all and only books with zero available copies. The aggregation ensures we handle multiple borrow records efficiently, and the ordering produces the required result format.

Python Solution

from typing import List, Dict
import pandas as pd

def find_books_with_no_available_copies(
    library_books: pd.DataFrame,
    borrowing_records: pd.DataFrame
) -> pd.DataFrame:
    active = borrowing_records[borrowing_records["return_date"].isna()]

    counts = (
        active.groupby("book_id")
	}

	var result []Book

	for _, b := range books {
		current := counts[b.BookID]
		if current == b.TotalCopies {
			b.CurrentBorrowers = current
			result = append(result, b)
		}
	}

	sort.Slice(result, func(i, j int) bool {
		if result[i].CurrentBorrowers == result[j].CurrentBorrowers {
			return result[i].Title < result[j].Title
		}
		return result[i].CurrentBorrowers > result[j].CurrentBorrowers
	})

	return result
}

In Go, we manually simulate SQL aggregation using a map keyed by book_id. We iterate over borrowing records once to compute active borrow counts. Then we iterate over books to apply the filtering condition and build the result list. Sorting is done using sort.Slice, ensuring we match the required ordering rules.

A key Go-specific detail is the use of a pointer for ReturnDate. This cleanly represents SQL NULL, allowing us to check nil to determine active borrow status.

Worked Examples

Using the sample input, we first process active borrowing records.

For book_id = 1, we see three active records: Alice Smith, Bob Johnson, and Grace Miller. This produces a count of 3.

For book_id = 3, we see one active record: David Brown. This produces a count of 1.

For book_id = 2, there are two active records, giving a count of 2, but total copies is 3, so it is not selected.

For book_id = 4, one active record exists, but total copies is 2, so it is not selected.

For book_id = 5, no active records exist, so count is 0.

For book_id = 6, one active record exists, but total copies is 4.

We then filter only books where current_borrowers == total_copies.

This leaves:

book_id	title	current_borrowers	total_copies
1	The Great Gatsby	3	3
3	1984	1	1

Sorting by current_borrowers DESC, then title ASC yields:

First: The Great Gatsby (3 borrowers)

Second: 1984 (1 borrower) import sqlite3 from typing import List, Tuple

def find_books_no_available_copies(conn: sqlite3.Connection) -> List[Tuple]: query = """ WITH current_borrowers_count AS ( SELECT book_id, COUNT(*) AS current_borrowers FROM borrowing_records WHERE return_date IS NULL GROUP BY book_id ) SELECT b.book_id, b.title, b.author, b.genre, b.publication_year, c.current_borrowers FROM library_books b JOIN current_borrowers_count c ON b.book_id = c.book_id WHERE c.current_borrowers = b.total_copies ORDER BY c.current_borrowers DESC, b.title ASC; """ cursor = conn.cursor() cursor.execute(query) return cursor.fetchall()

**Explanation:**

The `WITH` clause computes the number of current borrowers per book, reducing the need for repeated subqueries. We then join this aggregation with `library_books` to get book details and filter where the current borrowers equal total copies. Finally, the `ORDER BY` clause ensures the correct ordering.

## Go Solution

```go
package main

import (
    "database/sql"
    _ "github.com/mattn/go-sqlite3"
)

type Book struct {
    BookID            int
    Title             string
    Author            string
    Genre             string
    PublicationYear   int
    CurrentBorrowers  int
}

func FindBooksNoAvailableCopies(db *sql.DB) ([]Book, error) {
    query := `
    WITH current_borrowers_count AS (
        SELECT book_id, COUNT(*) AS current_borrowers
        FROM borrowing_records
        WHERE return_date IS NULL
        GROUP BY book_id
    )
    SELECT b.book_id, b.title, b.author, b.genre, b.publication_year, c.current_borrowers
    FROM library_books b
    JOIN current_borrowers_count c ON b.book_id = c.book_id
    WHERE c.current_borrowers = b.total_copies
    ORDER BY c.current_borrowers DESC, b.title ASC;
    `
    rows, err := db.Query(query)
    if err != nil {
        return nil, err
    }
    defer rows.Close()

    var books []Book
    for rows.Next() {
        var b Book
        if err := rows.Scan(&b.BookID, &b.Title, &b.Author, &b.Genre, &b.PublicationYear, &b.CurrentBorrowers); err != nil {
            return nil, err
        }
        books = append(books, b)
    }
    return books, nil
}

Go notes:

Go requires explicit struct definitions and row scanning. Handling of NULL in SQL is automatic when counting, and slices are used to store results. Error handling is explicit in Go, unlike Python's implicit exception propagation.

Worked Examples

For The Great Gatsby:

1. Filter borrowing_records → 3 NULL return_dates for book_id 1.
2. Group and count → 3 current borrowers.
3. Join with library_books → total_copies = 3.
4. Filter where current_borrowers = total_copies → included.
5. Ordered by current_borrowers DESC → appears first.

For 1984:

1. Only one borrowing with NULL return_date → 1 current borrower.
2. total_copies = 1 → included.
3. Appears after The Great Gatsby due to ordering.

Other books either have available copies remaining or fewer borrowers than total copies and are excluded.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(B + R)	Each record is scanned once to compute counts, then each book is processed once
Space	O(B)	Map stores at most one entry per book for active borrower counts

The linear complexity arises because both tables are traversed independently without nested scans. The grouping and hashing strategy ensures constant-time updates per record.

Test Cases

# provided-style structural tests (pandas-like logic simulated conceptually)

# Case 1: example scenario
assert True  # placeholder for full integration test

# Case 2: no active borrows
assert True  # all return_date non-null => empty result

# Case 3: all copies fully borrowed
assert True  # equality condition holds exactly

# Case 4: book missing from borrowing table
assert True  # should not appear since current_borrowers = 0 unless total_copies = 0

# Case 5: multiple active borrowers exceeding copies
assert True  # should be excluded since not equal
| Time | O(m + n) | m is number of borrowing records, n is number of books. Aggregation scans all borrowing records once, join scans books. |
| Space | O(n) | Store current borrower counts per book, proportional to the number of distinct books currently borrowed. |

The algorithm is efficient because it avoids nested loops and leverages database aggregation and join operations.

## Test Cases

Basic test with the example

assert find_books_no_available_copies(conn) == [ (1, "The Great Gatsby", "F. Scott", "Fiction", 1925, 3), (3, "1984", "George Orwell", "Dystopian", 1949, 1) ]

No borrowings

assert find_books_no_available_copies(conn_no_borrowings) == []

Book with 0 total copies

assert find_books_no_available_copies(conn_zero_copies) == []

Multiple books with same borrower count

assert find_books_no_available_copies(conn_same_count) == sorted_result

Single book borrowed

assert find_books_no_available_copies(conn_single_book) == [(5, "Sample Book", "Author", "Genre", 2020, 1)]

| Test | Why |
| --- | --- |
| Example input | Validates correctness and sorting |
| No active borrows | Ensures empty result handling |
| Exact match condition | Validates equality filter |
| Missing book in records | Ensures LEFT JOIN behavior |
| Over-borrow scenario | Ensures strict equality requirement |

## Edge Cases

One important edge case is when a book has no borrowing records at all. In this situation, the aggregation step produces no entry, so after the join we must treat its active borrower count as zero. This is handled via `COALESCE` in SQL or `fillna(0)` in pandas.

Another edge case is when all borrow records for a book have a non-NULL `return_date`. Even though the book exists in the borrowing table, it should still behave as if it has zero active borrowers, and thus only be included if its total copies is also zero.

A third edge case is when data inconsistencies cause the number of active borrowers to exceed total copies. The problem definition requires exact equality, so such books must be excluded even if they are logically overbooked. The filtering condition strictly enforces this invariant.
| Example | Validates main case |
| No borrowings | Handles empty borrowing_records |
| 0 total copies | Ensures books with zero copies are not included incorrectly |
| Same borrower count | Validates sorting logic |
| Single book borrowed | Validates minimal input |

## Edge Cases

**Edge Case 1: Books with zero copies**

Books with `total_copies = 0` should never appear since the library has no copies to lend. The algorithm handles this because `current_borrowers` cannot equal zero if there are no borrow records, and the join ensures no false positives.

**Edge Case 2: Multiple borrowers for a single-copy book**

If data integrity is violated and more borrow records exist than copies, the algorithm still correctly counts `current_borrowers` and will only include books where `current_borrowers = total_copies`, preventing overcounting from affecting the result.

**Edge Case 3: No books currently borrowed**

If all `return_date` fields are non-NULL, the aggregation produces an empty set. The join with `library_books` results in no rows returned, which is the expected behavior. This ensures the algorithm gracefully handles empty datasets without errors.