> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Design a Food Rating System Python Solution

> Tested Python solution for LeetCode 2353 with 15 pytest cases. Generate a practice environment with lcpy.

LeetCode 2353, [Medium](/catalog/medium). Topics: [Array](/catalog/topics/array), [Hash Table](/catalog/topics/hash-table), [String](/catalog/topics/string), [Design](/catalog/topics/design), [Heap (Priority Queue)](/catalog/topics/heap-priority-queue), [Ordered Set](/catalog/topics/ordered-set). [View on LeetCode](https://leetcode.com/problems/design-a-food-rating-system/description/).

Generate this problem as a practice environment: tested reference solution, 15 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 2353   # by problem number
lcpy gen -s design_a_food_rating_system   # by problem name
```

## Problem

Design a food rating system that can do the following:

* Modify the rating of a food item listed in the system.
* Return the highest-rated food item for a type of cuisine in the system.

Implement the `FoodRatings` class:

* `FoodRatings(String[] foods, String[] cuisines, int[] ratings)` Initializes the system. The food items are described by `foods`, `cuisines`, and `ratings`, all of which have a length of `n`.
  * `foods[i]` is the name of the `i`th food,
  * `cuisines[i]` is the type of cuisine of the `i`th food, and
  * `ratings[i]` is the initial rating of the `i`th food.
* `void changeRating(String food, int newRating)` Changes the rating of the food item with the name `food`.
* `String highestRated(String cuisine)` Returns the name of the food item that has the highest rating for the given type of cuisine. If there is a tie, return the item with the **lexicographically smaller** name.

Note that a string `x` is lexicographically smaller than string `y` if `x` comes before `y` in dictionary order, that is, either `x` is a prefix of `y`, or if `i` is the first position such that `x[i] != y[i]`, then `x[i]` comes before `y[i]` in alphabetic order.

### Examples

```
Input
["FoodRatings", "highestRated", "highestRated", "changeRating", "highestRated", "changeRating", "highestRated"]
[[["kimchi", "miso", "sushi", "moussaka", "ramen", "bulgogi"], ["korean", "japanese", "japanese", "greek", "japanese", "korean"], [9, 12, 8, 15, 14, 7]], ["korean"], ["japanese"], ["sushi", 16], ["japanese"], ["ramen", 16], ["japanese"]]
Output
[null, "kimchi", "ramen", null, "sushi", null, "ramen"]

Explanation
foodRatings.highestRated("korean"); // return "kimchi"
// "kimchi" is the highest rated korean food with a rating of 9.
foodRatings.highestRated("japanese"); // return "ramen"
// "ramen" is the highest rated japanese food with a rating of 14.
foodRatings.changeRating("sushi", 16); // "sushi" now has a rating of 16.
foodRatings.highestRated("japanese"); // return "sushi"
foodRatings.changeRating("ramen", 16); // "ramen" now has a rating of 16.
foodRatings.highestRated("japanese"); // return "ramen"
// Both "sushi" and "ramen" have a rating of 16.
// However, "ramen" is lexicographically smaller than "sushi".
```

### Constraints

* `1 <= n <= 2 * 10^4`
* `n == foods.length == cuisines.length == ratings.length`
* `1 <= foods[i].length, cuisines[i].length <= 10`
* `foods[i]`, `cuisines[i]` consist of lowercase English letters.
* `1 <= ratings[i] <= 10^8`
* All the strings in `foods` are **distinct**.
* `food` will be the name of a food item in the system across all calls to `changeRating`.
* `cuisine` will be a type of cuisine of **at least one** food item in the system across all calls to `highestRated`.
* At most `2 * 10^4` calls **in total** will be made to `changeRating` and `highestRated`.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/design_a_food_rating_system/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/design_a_food_rating_system/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
import heapq


class FoodRatings:
    # Time: init O(n), change_rating O(log n), highest_rated amortized O(log n)
    # Space: O(n) for the rating/cuisine maps and one lazy heap per cuisine
    def __init__(self, foods: list[str], cuisines: list[str], ratings: list[int]) -> None:
        self.rating: dict[str, int] = dict(zip(foods, ratings, strict=True))
        self.cuisine = dict(zip(foods, cuisines, strict=True))
        self.heaps: dict[str, list[tuple[int, str]]] = {}
        for food, cuisine, rating in zip(foods, cuisines, ratings, strict=True):
            self.heaps.setdefault(cuisine, []).append((-rating, food))
        for heap in self.heaps.values():
            heapq.heapify(heap)

    # Time: O(log n)
    # Space: O(1) amortized (each pushed entry is popped at most once)
    def change_rating(self, food: str, new_rating: int) -> None:
        self.rating[food] = new_rating
        # The old entry for this food is left behind as stale; highest_rated
        # discards entries whose rating no longer matches the current one.
        heapq.heappush(self.heaps[self.cuisine[food]], (-new_rating, food))

    # Time: O(log n) amortized
    # Space: O(1)
    def highest_rated(self, cuisine: str) -> str:
        heap = self.heaps[cuisine]
        while True:
            neg_rating, food = heap[0]
            if -neg_rating == self.rating[food]:
                return food
            heapq.heappop(heap)
```

## Complexity

| Time | Space |
| - | - |
| init O(n), change\_rating O(log n), highest\_rated amortized O(log n) | O(n) for the rating/cuisine maps and one lazy heap per cuisine |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.