2353. Design a Food Rating System LeetCode Solution

In this guide, you will get 2353. Design a Food Rating System LeetCode Solution with the best time and space complexity. The solution to Design a Food Rating System problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Design a Food Rating System solution in C++
4. Design a Food Rating System solution in Java
5. Design a Food Rating System solution in Python
6. Additional Resources

Problem Statement of Design a Food Rating System

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 ith food,
cuisines[i] is the type of cuisine of the ith food, and
ratings[i] is the initial rating of the ith 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.

Example 1:

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 foodRatings = new FoodRatings([“kimchi”, “miso”, “sushi”, “moussaka”, “ramen”, “bulgogi”], [“korean”, “japanese”, “japanese”, “greek”, “japanese”, “korean”], [9, 12, 8, 15, 14, 7]);
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”
// “sushi” is the highest rated japanese food with a rating of 16.
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 * 104
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] <= 108
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 * 104 calls in total will be made to changeRating and highestRated.

Complexity Analysis

• Time Complexity: O(\log n)
• Space Complexity: O(n)

2353. Design a Food Rating System LeetCode Solution in C++

class FoodRatings {
 public:
  FoodRatings(vector<string>& foods, vector<string>& cuisines,
              vector<int>& ratings) {
    for (int i = 0; i < foods.size(); ++i) {
      cuisineToRatingAndFoods[cuisines[i]].insert({-ratings[i], foods[i]});
      foodToCuisine[foods[i]] = cuisines[i];
      foodToRating[foods[i]] = ratings[i];
    }
  }

  void changeRating(string food, int newRating) {
    const string cuisine = foodToCuisine[food];
    const int oldRating = foodToRating[food];
    auto& ratingAndFoods = cuisineToRatingAndFoods[cuisine];
    ratingAndFoods.erase({-oldRating, food});
    ratingAndFoods.insert({-newRating, food});
    foodToRating[food] = newRating;
  }

  string highestRated(string cuisine) {
    return cuisineToRatingAndFoods[cuisine].begin()->second;
  }

 private:
  // {cuisine: {(-rating, food)}} stores negative rating for smarter comparison
  unordered_map<string, set<pair<int, string>>> cuisineToRatingAndFoods;
  unordered_map<string, string> foodToCuisine;
  unordered_map<string, int> foodToRating;
};
/* code provided by PROGIEZ */

2353. Design a Food Rating System LeetCode Solution in Java

class FoodRatings {
  public FoodRatings(String[] foods, String[] cuisines, int[] ratings) {
    for (int i = 0; i < foods.length; ++i) {
      cuisineToRatingAndFoods.putIfAbsent(
          cuisines[i],
          new TreeSet<>(
              Comparator.comparing(Pair<Integer, String>::getKey, Comparator.reverseOrder())
                  .thenComparing(Pair<Integer, String>::getValue)));
      cuisineToRatingAndFoods.get(cuisines[i]).add(new Pair<>(ratings[i], foods[i]));
      foodToCuisine.put(foods[i], cuisines[i]);
      foodToRating.put(foods[i], ratings[i]);
    }
  }

  public void changeRating(String food, int newRating) {
    final String cuisine = foodToCuisine.get(food);
    final int oldRating = foodToRating.get(food);
    TreeSet<Pair<Integer, String>> ratingAndFoods = cuisineToRatingAndFoods.get(cuisine);
    ratingAndFoods.remove(new Pair<>(oldRating, food));
    ratingAndFoods.add(new Pair<>(newRating, food));
    foodToRating.put(food, newRating);
  }

  public String highestRated(String cuisine) {
    return cuisineToRatingAndFoods.get(cuisine).first().getValue();
  }

  // {cuisine: {(rating, food)}}
  Map<String, TreeSet<Pair<Integer, String>>> cuisineToRatingAndFoods = new HashMap<>();
  Map<String, String> foodToCuisine = new HashMap<>();
  Map<String, Integer> foodToRating = new HashMap<>();
}
// code provided by PROGIEZ

2353. Design a Food Rating System LeetCode Solution in Python

from sortedcontainers import SortedSet


class FoodRatings:
  def __init__(self, foods: list[str], cuisines: list[str], ratings: list[int]):
    self.cuisineToRatingAndFoods = collections.defaultdict(
        lambda: SortedSet(key=lambda x: (-x[0], x[1])))
    self.foodToCuisine = {}
    self.foodToRating = {}

    for food, cuisine, rating in zip(foods, cuisines, ratings):
      self.cuisineToRatingAndFoods[cuisine].add((rating, food))
      self.foodToCuisine[food] = cuisine
      self.foodToRating[food] = rating

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

  def highestRated(self, cuisine: str) -> str:
    return self.cuisineToRatingAndFoods[cuisine][0][1]
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.