Problem Breakdown
Restatement: We need to filter a list of books where each book has an associated author_id, id, and sales_count. A book is considered “unpopular” if its individual sales count is strictly less than the average sales count calculated across all books by that specific author.
Inputs:
- List of dictionaries (
books) containing keys:id(int),author_id(int/str), andsales_count(int). - Constraints imply can be up to , necessitating an efficient solution better than nested loops.
Outputs:
- A list of integers representing the
ids of books that meet the “unpopular” criteria. Order is typically not specified unless required for sorting (we return as found or sorted).
Implicit Constraints & Edge Cases:
- Empty Input: Return empty list immediately if no books exist.
- Single Book per Author: The average equals the book’s sales count ( becomes , which is False), so it correctly excludes single-book authors from being “unpopular” under strict inequality logic.
- Floating Point Precision: Calculating averages using division introduces floating point numbers. Comparing integers to floats can occasionally lead to precision errors with very large sums. We will use integer arithmetic (cross-multiplication) in the solution for robustness ().
- Division by Zero: Since we aggregate first, every author present has at least one book (
count >= 1), making division safe or cross-multiplication safer.
Intuition
Naive Approach (Brute Force): For each book, calculate the average of its group repeatedly or compare against all other books in that group. This leads to time complexity due to repeated aggregation per query, which will Time Out on large inputs ().
Key Insight: The “average” for a specific author is constant regardless of how many times we check it. We can pre-calculate the total sales and count for each author_id in one pass to derive the average (or use cross-multiplication logic) once stored. This transforms the filtering step into an lookup per book during a second pass, resulting in overall time complexity.
Optimal Strategy:
- Aggregate: Iterate through all books once to sum
sales_countand count occurrences for eachauthor_id. Store these metrics in a hash map (defaultdict). - Filter: Iterate through the list of books again. For each book, retrieve its author’s pre-calculated total sales and count. Check if . If true, add to results.
Approach
- Initialize a
defaultdictnamedauthor_stats. Each entry will store{ 'total_sales': int, 'count': int }. - First Pass: Loop through the input
bookslist. For each book:- Extract
aid,sales_count. - Update
author_stats[aid]['total_sales'] += sales_count. - Increment
author_stats[aid]['count'].
- Extract
- Second Pass: Loop through the input
bookslist again to identify unpopular books:- Extract
book['id'],current_sales, andauthor_id. - Retrieve stats for that author from the map.
- Perform integer comparison check:
if current_sales * count < total_sales:(Avoids float precision issues). - If condition is met, append book ID to results list.
- Extract
- Return the collected IDs.
Complexity Analysis
- Time Complexity: where N is the number of books. We iterate through the
bookslist exactly twice. Dictionary operations (insertion and lookup) are amortized . Total time is linear relative to input size. - Space Complexity: where K is the number of unique authors stored in
author_stats, and M is the maximum possible result set size (). In standard scenarios, this simplifies to auxiliary space for storing author statistics.
Solution
from collections import defaultdict
from typing import List, Dict
def get_unpopular_books(books: List[Dict[str, int]]) -> List[int]:
"""
Identifies books that are 'unpopular' based on sales count relative to their author's average.
Args:
books: A list of dictionaries with keys 'id', 'author_id', and 'sales_count'.
Returns:
A list of book IDs where the individual sales count is strictly less than
the average sales count for that specific author (using integer arithmetic).
"""
if not books:
return []
# Step 1 & 2: Aggregate data per author in a single pass
# Stores {author_id: {'total_sales': int, 'count': int}}
author_stats = defaultdict(lambda: {'total_sales': 0, 'count': 0})
for book in books:
aid = book['author_id']
sales = book['sales_count']
# Accumulate totals and counts to calculate average later
author_stats[aid]['total_sales'] += sales
author_stats[aid]['count'] += 1
unpopular_ids = []
# Step 3 & 4: Filter books based on calculated averages in a second pass
for book in books:
aid = book['author_id']
current_sales = book['sales_count']
stats = author_stats[aid]
total_sales = stats['total_sales']
count = stats['count']
# Use integer arithmetic to avoid floating point precision issues.
# Condition: sales < (total / count) <=> sales * count < total
if current_sales * count < total_sales:
unpopular_ids.append(book['id'])
return unpopular_ids