LeetCode 2353 - Design a Food Rating System

LeetCode Problem 2353

Difficulty: 🟡 Medium
Topics: Array, Hash Table, String, Design, Heap (Priority Queue), Ordered Set

Solution

Problem Understanding

The problem is asking us to implement a food rating system that supports dynamic updates to the ratings of individual food items and allows querying for the highest-rated food for a given cuisine. Each food has a unique name, belongs to exactly one cuisine, and has an associated rating. The system must efficiently handle two operations: changeRating, which updates the rating of a specified food, and highestRated, which returns the food with the highest rating for a particular cuisine, breaking ties lexicographically by food name.

The input consists of three parallel arrays: foods, cuisines, and ratings, each of length n. foods[i] gives the name of the i-th food, cuisines[i] the cuisine type, and ratings[i] the initial rating. The constraints indicate n can be up to 20,000 and there can be up to 20,000 combined operations, so a naive approach that scans all foods for each query would be too slow. The uniqueness of food names ensures that we can directly identify a food with a hash map, and the guarantees about cuisine presence simplify error handling in queries.

Important edge cases include: multiple foods having the same highest rating (requiring lexicographic comparison), updating a rating to become the new maximum for a cuisine, and rapidly changing ratings multiple times for the same food.

Approaches

Brute Force Approach

The simplest solution is to store the foods and their ratings in a hash map and, for each highestRated query, iterate over all foods of the specified cuisine to find the maximum rating. Updating a food’s rating is straightforward: simply replace the value in the hash map. This approach is correct, but the query operation requires scanning potentially all n foods, giving O(n) time complexity per highestRated call, which is too slow for the upper bounds of the problem.

Optimal Approach

The optimal approach relies on maintaining a max-heap (priority queue) for each cuisine, storing tuples of negative rating and food name. By using a heap, we can efficiently query the highest-rated food in O(1) for retrieval and O(log n) for updates. Since Python heaps do not support direct update, we handle rating changes by pushing the new rating into the heap while keeping the old one; when extracting the max, we skip over outdated entries using a hash map that records the current rating of each food. This ensures both changeRating and highestRated are efficient. Lexicographic tie-breaking is handled by the heap storing food names along with negative ratings, which naturally orders them correctly.

Algorithm Walkthrough

1. Initialize a hash map foodToCuisine mapping each food name to its cuisine type. This allows quick lookup of the cuisine when updating ratings.
2. Initialize a hash map foodToRating mapping each food name to its current rating. This stores the authoritative rating for each food.
3. Initialize a hash map cuisineHeap mapping each cuisine to a max-heap of tuples (-rating, foodName). Negative ratings are used so that the heap operates as a max-heap.
4. For each initial food in foods, insert a tuple (-ratings[i], foods[i]) into the corresponding cuisine heap and populate the rating map.
5. To changeRating(food, newRating), update the food's rating in foodToRating and push (-newRating, food) into the corresponding cuisine heap. We do not remove old ratings immediately; they are lazily ignored when querying.
6. To highestRated(cuisine), peek at the top of the heap. If the rating in foodToRating matches the negative of the stored heap rating, return the food. Otherwise, pop outdated entries until the top of the heap matches the current rating.

Why it works: The heap guarantees that the tuple with the highest rating (and lexicographically smallest name for ties) is always near the top. Lazy deletion ensures we do not waste time removing outdated entries, while the authoritative foodToRating map guarantees correctness.

Python Solution

from typing import List
import heapq

class FoodRatings:

    def __init__(self, foods: List[str], cuisines: List[str], ratings: List[int]):
        self.foodToCuisine = {}
        self.foodToRating = {}
        self.cuisineHeap = {}

        for food, cuisine, rating in zip(foods, cuisines, ratings):
            self.foodToCuisine[food] = cuisine
            self.foodToRating[food] = rating
            if cuisine not in self.cuisineHeap:
                self.cuisineHeap[cuisine] = []
            heapq.heappush(self.cuisineHeap[cuisine], (-rating, food))

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

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

This implementation maintains a separate heap per cuisine for fast retrieval of the highest-rated food. Changing ratings is done by adding new entries, while outdated entries are lazily removed when querying.

Go Solution

package main

import (
    "container/heap"
)

type FoodEntry struct {
    rating int
    name   string
}

type FoodHeap []FoodEntry

func (h FoodHeap) Len() int { return len(h) }
func (h FoodHeap) Less(i, j int) bool {
    if h[i].rating == h[j].rating {
        return h[i].name < h[j].name
    }
    return h[i].rating > h[j].rating
}
func (h FoodHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }

func (h *FoodHeap) Push(x any) { *h = append(*h, x.(FoodEntry)) }
func (h *FoodHeap) Pop() any {
    old := *h
    n := len(old)
    item := old[n-1]
    *h = old[:n-1]
    return item
}

type FoodRatings struct {
    foodToCuisine map[string]string
    foodToRating  map[string]int
    cuisineHeap   map[string]*FoodHeap
}

func Constructor(foods []string, cuisines []string, ratings []int) FoodRatings {
    fr := FoodRatings{
        foodToCuisine: make(map[string]string),
        foodToRating:  make(map[string]int),
        cuisineHeap:   make(map[string]*FoodHeap),
    }
    for i := range foods {
        food, cuisine, rating := foods[i], cuisines[i], ratings[i]
        fr.foodToCuisine[food] = cuisine
        fr.foodToRating[food] = rating
        if _, exists := fr.cuisineHeap[cuisine]; !exists {
            h := &FoodHeap{}
            heap.Init(h)
            fr.cuisineHeap[cuisine] = h
        }
        heap.Push(fr.cuisineHeap[cuisine], FoodEntry{rating, food})
    }
    return fr
}

func (fr *FoodRatings) ChangeRating(food string, newRating int) {
    cuisine := fr.foodToCuisine[food]
    fr.foodToRating[food] = newRating
    heap.Push(fr.cuisineHeap[cuisine], FoodEntry{newRating, food})
}

func (fr *FoodRatings) HighestRated(cuisine string) string {
    h := fr.cuisineHeap[cuisine]
    for {
        top := (*h)[0]
        if fr.foodToRating[top.name] == top.rating {
            return top.name
        }
        heap.Pop(h)
    }
}

Go implementation uses a custom FoodHeap type with a max-heap property, maintaining the same lazy deletion logic as in Python.

Worked Examples

Initial State:

1. highestRated("korean") returns kimchi.
2. highestRated("japanese") returns ramen.
3. changeRating("sushi", 16) updates sushi; heap now contains (-16, sushi).
4. highestRated("japanese") returns sushi.
5. changeRating("ramen", 16) updates ramen; heap now has (-16, sushi) and (-16, ramen).
6. highestRated("japanese") returns ramen due to lexic