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 leastmovie_idandrating. 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_idand calculatedaverage_rating.
Constraints & Edge Cases:
- Empty Input: If no ratings exist, return an empty list or handle gracefully without crashing.
- 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_idascending for ties to ensure a unique result. - Rating Values: Ratings are typically floats or integers between 1 and 5. Division must handle integer division correctly in Python (use
/). - Data Volume: Large datasets require aggregation rather than nested loops ().
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 (), we can derive averages immediately after processing or during iteration.
Optimal Approach:
- Accumulate: Iterate through all ratings once. Maintain
sum_ratingandcountpermovie_id. - Derive Average: Compute average = sum / count for each movie post-aggregation.
- 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
- Initialize Storage: Create a dictionary (
defaultdictor standard dict) where keys are unique movie IDs and values store tuples/lists of(sum_ratings, count_reviews). - Aggregate Data: Loop through the input
ratingslist. Extractmovie_idandrating, updating the corresponding accumulator in storage. - 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).
- 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_idascending. Return the top result(s) as a formatted dictionary or tuple depending on expected output schema, typically[{'movie_id': ..., 'rating': ...}].
Complexity Analysis
- Time Complexity: to iterate through all rating records and populate aggregates ( is total ratings). Calculating averages takes where is unique movies. Sorting takes . Since , the dominant term for large inputs remains linear-logarithmic relative to input size, effectively dominated by aggregation: .
- Space Complexity: 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
ratingsdoes not execute;movie_statsremains empty, and the function returns an empty list immediately after checking ifmovies_with_avgis 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_idascending (via-rating, thenid). 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.