Domain 2MediumMEDIUM

Movie Rating

Aggregate ratings per movie using a hash map to simulate SQL GROUP BY, calculate averages in O(1), and sort by average rating descending with deterministic tie-breaking.

Domain: medium•Updated: 2026-09-14
#hash_map#group_by#sorting#O(N)

Problem Breakdown

Restatement: The objective is to find the movie(s) possessing the highest mean user satisfaction score. This requires aggregating individual ratings associated with each unique movie_id, computing their arithmetic means, and selecting the top performer based on these metrics. In a SQL context (e.g., LeetCode 1964), this involves joining tables or processing joined data to group by movie ID.

Inputs & Outputs:

  • Input: A collection of rating records (ratings). Each record contains at least movie_id and rating. The input format is assumed to be a list of dictionaries for Python simulation, though tuple support can be added if necessary.
  • Output: A single movie (or top N) with the highest average rating. Standard practice requires returning specific fields like movie_id and calculated average_rating.

Constraints & Edge Cases:

  1. Empty Input: If no ratings exist, return an empty list or handle gracefully without crashing.
  2. Ties in Average Rating: Deterministic behavior is required (e.g., if multiple movies share the highest average rating). Standard SQL/LeetCode convention often dictates sorting by movie_id ascending for ties to ensure a unique result.
  3. Rating Values: Ratings are typically floats or integers between 1 and 5. Division must handle integer division correctly in Python (use /).
  4. Data Volume: Large datasets require O(N)O(N) aggregation rather than nested loops (O(M×N)O(M \times N)).

Intuition

Brute Force Approach: Iterating through all movies to recalculate their average for every query or comparing pairs leads to high complexity and redundant calculations. This is inefficient as it ignores the associative property of summation.

Key Insight: The problem maps directly to SQL’s GROUP BY clause combined with aggregate functions (AVG, COUNT). In Python, a Hash Map (Dictionary) serves this purpose efficiently. By accumulating sums and counts for each movie in a single pass over the data (O(N)O(N)), we can derive averages immediately after processing or during iteration.

Optimal Approach:

  1. Accumulate: Iterate through all ratings once. Maintain sum_rating and count per movie_id.
  2. Derive Average: Compute average = sum / count for each movie post-aggregation.
  3. Rank & Filter: Sort the list of movies by their computed averages in descending order. Apply a secondary sort key (e.g., movie_id) to handle ties deterministically, ensuring consistent output across different environments.

Approach

  1. Initialize Storage: Create a dictionary (defaultdict or standard dict) where keys are unique movie IDs and values store tuples/lists of (sum_ratings, count_reviews).
  2. Aggregate Data: Loop through the input ratings list. Extract movie_id and rating, updating the corresponding accumulator in storage.
  3. Calculate Averages & Prepare for Sorting: Iterate over the accumulated stats to compute floating-point averages. Store these alongside movie IDs, ensuring we handle division by zero (though count > 0 check is implicit if input has ratings).
  4. Sort & Select: Sort the list of movies based on average rating descending. To ensure deterministic results in case of ties (common requirement), sort secondary key by movie_id ascending. Return the top result(s) as a formatted dictionary or tuple depending on expected output schema, typically [{'movie_id': ..., 'rating': ...}].

Complexity Analysis

  • Time Complexity: O(N)O(N) to iterate through all rating records and populate aggregates (NN is total ratings). Calculating averages takes O(M)O(M) where MM is unique movies. Sorting takes O(Mlog⁡M)O(M \log M). Since M≤NM \le N, the dominant term for large inputs remains linear-logarithmic relative to input size, effectively dominated by aggregation: O(N+Mlog⁡M)O(N + M \log M).
  • Space Complexity: O(M)O(M) to store the sum and count aggregates in the hash map. This is optimal as we must retain state for every unique movie with ratings.

Solution

from collections import defaultdict

def get_top_rated_movies(ratings):
    """
    Simulates SQL aggregation logic: 
    1. GROUP BY movie_id (using dict)
    2. Calculate AVG(RATING) per group
    3. ORDER BY avg_rating DESC, movie_id ASC
    
    Args:
        ratings: List of dicts like {'movie_id': int, 'rating': float} or tuples [id, rating]
    
    Returns:
        A list containing the top rated movie(s). 
        Format: [{'movie_id': id, 'average_rating': avg}] (or empty if none)
    """
    
    # Step 1 & 2: Aggregate data in one pass using a dictionary
    # Using defaultdict to simplify initialization of sum and count
    movie_stats = defaultdict(lambda: {'sum_rating': 0.0, 'count': 0})
    
    for record in ratings:
        # Handle flexible input format (dict or tuple) if necessary 
        # Standardizing on dict access based on docstring assumption
        try:
            mid = record['movie_id']
            rating = record['rating']
        except TypeError:
            # Fallback logic for tuples [user, movie_id, rating] -> adjust indices as needed
            # Assuming tuple format (id, rating) or similar based on context. 
            # For robustness in this solution, we assume dict structure per docstring.
            mid = record[1] if len(record) > 0 else None
            rating = record[2] if len(record) > 2 else 0
            
        movie_stats[mid]['sum_rating'] += float(rating)
        movie_stats[mid]['count'] += 1
        
    # Step 3: Calculate averages and prepare for sorting
    movies_with_avg = []
    
    for mid, stats in movie_stats.items():
        if stats['count'] > 0:
            avg_rating = stats['sum_rating'] / stats['count']
            # Store tuple (avg_rating, movie_id) to sort later. 
            # We will convert this back to dict at the end or return directly.
            movies_with_avg.append({'movie_id': mid, 'average_rating': avg_rating}) 
            
    # Step 4: Sort descending by average rating, then ascending by movie_id for ties
    if not movies_with_avg:
        return []

    # Sorting key: primary -avg (descending), secondary id (ascending) 
    # Using negative float for descending sort on first element without reverse flag confusion
    movies_with_avg.sort(key=lambda x: (-x['average_rating'], x['movie_id'])) 
    
    # Return only the top result as per typical "highest average" requirement, 
    # or return all if multiple exist. Usually LC expects just one movie ID/rating pair.
    return [movies_with_avg[0]]

# Example usage simulation (not part of function signature required by prompt)
if __name__ == "__main__":
    data = [
        {'movie_id': 102, 'rating': 4}, 
        {'movie_id': 103, 'rating': 5}, 
        {'movie_id': 102, 'rating': 5} # Avg for 102 becomes (9/2 = 4.5)
    ]
    print(get_top_rated_movies(data))

Edge Cases Handled

  • Empty Ratings List: The loop over ratings does not execute; movie_stats remains empty, and the function returns an empty list immediately after checking if movies_with_avg is empty. This prevents errors on division by zero or sorting empty lists.
  • Single Movie/Record: Logic holds as count becomes 1 and sum equals rating, resulting in average = rating. Sorting works correctly with a single element.
  • Tie-Breaking: The sort key explicitly handles ties using movie_id ascending (via -rating, then id). This ensures deterministic output even if multiple movies share the exact same highest average rating, adhering to standard SQL tie-breaking conventions for unique results.
  • Data Types: Ratings are cast to float (float(rating)) before summation and division to ensure accurate decimal averages regardless of input integer/float type.