Design a Food Rating System
Last Updated: April 4, 2026
Understanding the Problem
We need to build a data structure that manages food items, each belonging to a cuisine and having a rating. Two operations must be supported: updating a food's rating and querying the highest-rated food for a given cuisine (with lexicographic tiebreaking).
The interesting challenge here is the interplay between updates and queries. If we only needed queries, we could sort each cuisine's food list once and be done. But ratings change, so we need a structure that handles both efficiently. The naive approach would scan all foods in a cuisine on every query, but with up to 2 * 10^4 total calls, we want something faster.
The key observation is that we need a per-cuisine ordered collection where we can quickly find the maximum and also update individual elements. This is a classic use case for sorted sets (like TreeSet in Java or SortedList in Python) or heaps with lazy deletion.
Key Constraints:
n <= 2 * 10^4andat most 2 * 10^4 calls-> Total operations are at most ~4 10^4. Even O(n) per operation would give ~4 10^8, which is borderline. O(n log n) per operation is safe, but O(n^2) total is too slow.All food names are distinct-> We can use food names as unique keys in hash maps.food will always be valid-> No need to handle missing food names in changeRating.cuisine will always be valid-> No need to handle empty cuisines in highestRated.
Approach 1: Brute Force (Linear Scan)
Intuition
The simplest design: store each food's information in hash maps and, whenever we need the highest-rated food for a cuisine, just scan through all foods of that cuisine and pick the best one. No fancy data structures, no ordering to maintain. It's straightforward and correct.
For changeRating, we just update the food's rating in a hash map. That's O(1). For highestRated, we iterate through all foods belonging to the given cuisine, compare ratings, and handle tiebreaking by name. This scan is O(k) where k is the number of foods in that cuisine.
Algorithm
- In the constructor, build three hash maps:
foodToRating: maps each food name to its rating.foodToCuisine: maps each food name to its cuisine.cuisineToFoods: maps each cuisine to its list of food names.- For
changeRating(food, newRating): updatefoodToRating[food]tonewRating. - For
highestRated(cuisine): iterate through all foods incuisineToFoods[cuisine], track the one with the highest rating. If two foods have the same rating, pick the lexicographically smaller name.
Example Walkthrough
Code
- Time Complexity:
- Constructor: O(n), where n is the number of food items. We iterate once to populate all hash maps.
changeRating: O(1). Single hash map update.highestRated: O(k), where k is the number of foods in the given cuisine. In the worst case, all foods belong to one cuisine, so k = n.- Space Complexity: O(n) for storing all food information in hash maps.
Every highestRated call scans through every food in the requested cuisine. If one cuisine has thousands of foods and we make thousands of queries, we're doing redundant work. What if we could maintain the foods in sorted order so that the highest-rated one is always immediately accessible?
Approach 2: Sorted Set (Optimal)
Intuition
Instead of scanning all foods on every query, we can maintain a sorted set for each cuisine. The sorted set keeps food items ordered by rating (descending) and then by name (ascending for tiebreaking). This way, the highest-rated food is always at the front of the set, giving us O(1) query time (just peek at the first element).
The trick is handling changeRating. When a food's rating changes, we can't just update the value in place because sorted sets are ordered by the value. We need to remove the old entry (old rating, food name), update the rating, then insert the new entry (new rating, food name). Both removal and insertion are O(log k) in a balanced BST-backed sorted set, where k is the number of foods in that cuisine.
In Java, TreeSet is perfect for this. We define a custom comparator that sorts by rating descending, then by name ascending. In Python, we use SortedList from the sortedcontainers library (which LeetCode supports). In C++, we use set with a custom comparator or store pairs sorted appropriately.
Algorithm
- In the constructor:
- Build a
foodToRatingmap and afoodToCuisinemap, same as before. - For each cuisine, create a
TreeSet(or equivalent sorted set) that orders entries by (-rating, name). This way the first element is always the highest-rated food (with lexicographic tiebreaking). - For
changeRating(food, newRating): - Look up the food's cuisine and current rating.
- Remove the entry (currentRating, food) from the cuisine's sorted set.
- Update
foodToRating[food]to newRating. - Insert the entry (newRating, food) into the cuisine's sorted set.
- For
highestRated(cuisine): - Return the first element of the cuisine's sorted set. This is the food with the highest rating (and smallest name on ties).
Example Walkthrough
Code
The sorted set maintains foods in the exact order we need: highest rating first, with lexicographic tiebreaking. By storing entries as (-rating, name) pairs (or using a custom comparator), the natural ordering of the set matches our query requirements. The first element is always the answer to highestRated.
When we change a rating, we remove the old entry and insert the new one. This is safe because sorted sets guarantee that after removal and insertion, the ordering invariant is maintained. The key insight is that we must remove before updating the rating (since the set's ordering depends on the rating value), then re-insert after.
For languages without a built-in TreeSet (Go, JavaScript, TypeScript), we use a heap with lazy deletion. Instead of removing the old entry (which is expensive in a heap), we just push a new entry and mark the old one as stale. During queries, we pop stale entries off the top until we find a valid one. This gives amortized O(log n) per operation.
- Time Complexity:
- Constructor: O(n log n). For each of the n foods, we insert into a sorted set, which takes O(log k) where k is the number of foods in that cuisine. Across all foods, this sums to O(n log n) in the worst case.
changeRating: O(log n). One removal and one insertion in the sorted set, each O(log k) where k <= n.highestRated: O(1) for TreeSet (just peek at the first element). For the heap variant, it's amortized O(log n) due to lazy deletion.- Space Complexity: O(n) for the hash maps and sorted sets. For the heap variant, space can grow to O(n + q) where q is the number of changeRating calls, since stale entries remain in the heap until they're lazily removed.