2353. Design a Food Rating System - Explanation

Problem Link



Prerequisites

Before attempting this problem, you should be comfortable with:

  • Hash Maps - Storing and retrieving key-value pairs in O(1) time
  • Heaps / Priority Queues - Efficiently accessing the maximum or minimum element
  • Sorted Sets / TreeSets - Maintaining elements in sorted order with efficient insertion and deletion
  • Lazy Deletion - Marking entries as invalid rather than removing them immediately from data structures

1. Brute Force

Intuition

The simplest approach stores each food's rating in a hash map and groups foods by their cuisine in another hash map. When we need the highest-rated food for a cuisine, we scan through all foods in that cuisine and find the maximum. This is straightforward but inefficient for frequent queries since we examine every food each time.

Algorithm

  1. During initialization, create two hash maps:
    • foodToRating: maps each food name to its rating.
    • cuisineToFood: maps each cuisine to a list of foods belonging to it.
  2. For changeRating(food, newRating): update the rating in foodToRating.
  3. For highestRated(cuisine): iterate through all foods in the cuisine, track the one with the highest rating (breaking ties by lexicographically smallest name), and return it.
class FoodRatings:

    def __init__(self, foods: List[str], cuisines: List[str], ratings: List[int]):
        self.foodToRating = {} # food -> rating
        self.cuisineToFood = defaultdict(list) # cuisine -> [food]
        for i in range(len(foods)):
            self.foodToRating[foods[i]] = ratings[i]
            self.cuisineToFood[cuisines[i]].append(foods[i])

    def changeRating(self, food: str, newRating: int) -> None:
        self.foodToRating[food] = newRating

    def highestRated(self, cuisine: str) -> str:
        maxR, res = 0, ""
        for food in self.cuisineToFood[cuisine]:
            r = self.foodToRating[food]
            if r > maxR or (r == maxR and food < res):
                res = food
                maxR = r
        return res

Time & Space Complexity

  • Time complexity:
    • O(n)O(n) time for initialization.
    • O(1)O(1) time for each changeRating()changeRating() function call.
    • O(n)O(n) time for each highestRated()highestRated() function call.
  • Space complexity: O(n)O(n)

2. Heap

Intuition

Using a max-heap (priority queue) for each cuisine allows us to quickly access the highest-rated food. The challenge is handling rating updates: removing an element from the middle of a heap is expensive. Instead, we use lazy deletion. When a rating changes, we push a new entry with the updated rating. When querying, we check if the top entry's rating matches the current rating in our hash map. If not, it is stale, and we pop it until we find a valid entry.

Algorithm

  1. During initialization, create three structures:
    • foodToRating: maps food to its current rating.
    • foodToCuisine: maps food to its cuisine.
    • cuisineToHeap: maps each cuisine to a max-heap of (rating, food) pairs, ordered by rating descending then food name ascending.
  2. For changeRating(food, newRating): update foodToRating and push the new (rating, food) pair onto the cuisine's heap.
  3. For highestRated(cuisine): peek at the top of the heap. If the rating matches what is in foodToRating, return the food. Otherwise, pop the stale entry and repeat.
class FoodRatings:

    def __init__(self, foods: List[str], cuisines: List[str], ratings: List[int]):
        self.foodToRating = {}  # food -> rating
        self.foodToCuisine = {}  # food -> cuisine
        self.cuisineToHeap = defaultdict(list)  # cuisine -> max_heap

        for i in range(len(foods)):
            self.foodToRating[foods[i]] = ratings[i]
            self.foodToCuisine[foods[i]] = cuisines[i]
            heappush(self.cuisineToHeap[cuisines[i]], (-ratings[i], foods[i]))

    def changeRating(self, food: str, newRating: int) -> None:
        cuisine = self.foodToCuisine[food]
        self.foodToRating[food] = newRating
        heappush(self.cuisineToHeap[cuisine], (-newRating, food))

    def highestRated(self, cuisine: str) -> str:
        heap = self.cuisineToHeap[cuisine]
        while heap:
            rating, food = heap[0]
            if -rating == self.foodToRating[food]:
                return food
            heappop(heap)

Time & Space Complexity

  • Time complexity:
    • O(nlog⁡n)O(n \log n) time for initialization.
    • O(log⁡n)O(\log n) time for each changeRating()changeRating() function call.
    • O(log⁡n)O(\log n) time for each highestRated()highestRated() function call.
  • Space complexity: O(n)O(n)

3. Sorted Set

Intuition

A sorted set (like TreeSet or SortedSet) maintains elements in sorted order and supports efficient insertion, deletion, and access to the minimum/maximum element. For each cuisine, we store (negative rating, food name) pairs so the smallest element corresponds to the highest rating. When updating a rating, we remove the old entry and insert the new one. Querying simply returns the first element of the set.

Algorithm

  1. During initialization, create three structures:
    • foodToRating: maps food to its current rating.
    • foodToCuisine: maps food to its cuisine.
    • cuisineToSortedSet: maps each cuisine to a sorted set of (negative rating, food) pairs.
  2. For changeRating(food, newRating): remove the old (negative old rating, food) pair from the set, update foodToRating, and insert the new (negative new rating, food) pair.
  3. For highestRated(cuisine): return the food name from the first element in the sorted set (which has the highest rating due to the negative sign).
class FoodRatings:

    def __init__(self, foods: List[str], cuisines: List[str], ratings: List[int]):
        self.foodToRating = {} # food -> rating
        self.foodToCuisine = {} # food -> cuisine
        self.cuisineToSortedSet = defaultdict(SortedSet) # cuisine -> SortedSet[(rating, food)]

        for i in range(len(foods)):
            self.foodToRating[foods[i]] = ratings[i]
            self.foodToCuisine[foods[i]] = cuisines[i]
            self.cuisineToSortedSet[cuisines[i]].add((-ratings[i], foods[i]))

    def changeRating(self, food: str, newRating: int) -> None:
        cuisine = self.foodToCuisine[food]
        oldRating = self.foodToRating[food]

        self.cuisineToSortedSet[cuisine].remove((-oldRating, food))
        self.foodToRating[food] = newRating
        self.cuisineToSortedSet[cuisine].add((-newRating, food))

    def highestRated(self, cuisine: str) -> str:
        return self.cuisineToSortedSet[cuisine][0][1]

Time & Space Complexity

  • Time complexity:
    • O(nlog⁡n)O(n \log n) time for initialization.
    • O(log⁡n)O(\log n) time for each changeRating()changeRating() function call.
    • O(1)O(1) in Python and O(log⁡n)O(\log n) in other languages for each highestRated()highestRated() function call.
  • Space complexity: O(n)O(n)

Common Pitfalls

Forgetting to Handle Lexicographic Tie-Breaking

When multiple foods have the same highest rating, you must return the lexicographically smallest name. Forgetting this tie-breaker or sorting in the wrong order will produce incorrect results.

# Wrong: Only compares ratings
if r > maxR:
    res = food
    maxR = r

# Correct: Include lexicographic comparison for ties
if r > maxR or (r == maxR and food < res):
    res = food
    maxR = r

Not Removing Stale Entries from the Heap

When using a heap with lazy deletion, you must validate that the top entry's rating matches the current rating in your hash map before returning it. Stale entries from previous rating updates will otherwise be returned.

# Wrong: Returns potentially stale entry
def highestRated(self, cuisine):
    return self.cuisineToHeap[cuisine][0][1]  # May be outdated!

# Correct: Validate and remove stale entries
def highestRated(self, cuisine):
    heap = self.cuisineToHeap[cuisine]
    while heap:
        rating, food = heap[0]
        if -rating == self.foodToRating[food]:
            return food
        heappop(heap)  # Remove stale entry

Forgetting to Map Food to Its Cuisine

When a rating changes, you need to know which cuisine the food belongs to in order to update the correct data structure. Without a foodToCuisine mapping, you cannot efficiently locate and update the food's entry.

# Wrong: No way to find cuisine when rating changes
def changeRating(self, food, newRating):
    self.foodToRating[food] = newRating
    # How do we update the heap? We don't know the cuisine!

# Correct: Maintain food-to-cuisine mapping
def __init__(self, foods, cuisines, ratings):
    self.foodToCuisine = {}  # food -> cuisine
    for i in range(len(foods)):
        self.foodToCuisine[foods[i]] = cuisines[i]