Domain 2MediumMEDIUM

Unpopular Books

Identifies books with sales below their author's average using a two-pass hash map aggregation strategy to achieve linear time complexity.

Domain: medium•Updated: 2026-09-08
#hash map#aggregation#O(N) time complexity#O(K) space complexity

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), and sales_count (int).
  • Constraints imply NN can be up to 10510^5, 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 (sales<avgsales < avg becomes x<xx < x, 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 (sales×count<totalsales \times count < total).
  • 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 O(N2)O(N^2) time complexity due to repeated aggregation per query, which will Time Out on large inputs (N=105N=10^5).

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 O(1)O(1) lookup per book during a second pass, resulting in overall O(N)O(N) time complexity.

Optimal Strategy:

  1. Aggregate: Iterate through all books once to sum sales_count and count occurrences for each author_id. Store these metrics in a hash map (defaultdict).
  2. Filter: Iterate through the list of books again. For each book, retrieve its author’s pre-calculated total sales and count. Check if current_sales×group_count<group_totalcurrent\_sales \times group\_count < group\_total. If true, add to results.

Approach

  1. Initialize a defaultdict named author_stats. Each entry will store { 'total_sales': int, 'count': int }.
  2. First Pass: Loop through the input books list. For each book:
    • Extract aid, sales_count.
    • Update author_stats[aid]['total_sales'] += sales_count.
    • Increment author_stats[aid]['count'].
  3. Second Pass: Loop through the input books list again to identify unpopular books:
    • Extract book['id'], current_sales, and author_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.
  4. Return the collected IDs.

Complexity Analysis

  • Time Complexity: O(N)O(N) where N is the number of books. We iterate through the books list exactly twice. Dictionary operations (insertion and lookup) are amortized O(1)O(1). Total time is linear relative to input size.
  • Space Complexity: O(K+M)O(K + M) where K is the number of unique authors stored in author_stats, and M is the maximum possible result set size (M≤NM \le N). In standard scenarios, this simplifies to O(N)O(N) 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