Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Queries compare foods only within one cuisine, so maintain a separate ordered collection per cuisine. Sorting by negative rating makes the greatest rating come first, while the food name provides the required lexicographical tie-break.

Approach

Store (-rating, food) in its cuisine's collection and keep a lookup from food to its current rating and cuisine. To change a rating, remove the exact old tuple, insert the updated tuple, and update the lookup. To find the highest-rated food, return the name in the cuisine's first tuple. Removing the old record prevents stale ratings from affecting future queries; food names break equal-rating ties consistently.

class FoodRatings:
    def __init__(self, foods: List[str], cuisines: List[str], ratings: List[int]):
        self.cuisines_info = defaultdict(SortedList)
        self.food_info = {}
        n = len(foods)

        for i in range(n):
            self.cuisines_info[cuisines[i]].add((-ratings[i], foods[i]))
            self.food_info[foods[i]] = (-ratings[i], cuisines[i])

    def changeRating(self, food: str, newRating: int) -> None:
        old_r, c = self.food_info[food]
        self.food_info[food] = (-newRating, c)
        self.cuisines_info[c].discard((old_r, food))
        self.cuisines_info[c].add((-newRating, food))

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

Complexity analysis

Let n = foods.length and c be the number of foods in the affected cuisine. Names have at most ten characters, so comparison/hashing costs are bounded here. With expected constant-time map lookups, JavaScript construction takes O(n log(n + 1)), changeRating takes O(log(c + 1)) worst-case tree work, and highestRated takes O(1) via the stored head. Its iterative AVL operations use O(1) transient state. Python SortedList offers approximately logarithmic updates in practice, not strict worst-case logarithmic guarantees: block shifts/splits can make an individual update O(c), yielding a conservative O(n^2) construction bound. Its first-element lookup is O(1). Both retain O(n) persistent state; Python block maintenance can use up to O(c) temporary storage.