Filter Restaurants By Vegan Friendly Price And Distance - Leetcode Solution

Problem Statement:

Given a list of restaurants with their locations, ratings and prices, filter the restaurants based on whether they are vegan friendly, their maximum price and maximum distance from a given location. Return the restaurants that meet the criteria sorted in descending order by their rating. If multiple restaurants have the same rating, sort them in ascending order by their name.

Function Signature:

def filterRestaurants(restaurants: List[List[int]], veganFriendly: int, maxPrice: int, maxDistance: int) -> List[int]:

Input

• restaurants: List[List[int]] - A list of n elements containing n lists of the form [id, rating, veganFriendly, price, distance] where 1 <= n <= 10^4.
• veganFriendly: An integer representing the minimum level of vegan friendliness required for a restaurant (0 or 1).
• maxPrice: An integer representing the maximum price for a meal at a restaurant (1 <= maxPrice <= 10^5).
• maxDistance: An integer representing the maximum distance from the given location to a restaurant (1 <= maxDistance <= 10^5).

Output

A list of restaurant IDs sorted in descending order by their rating. If multiple restaurants have the same rating, sort them in ascending order by their name.

Example:

Input:

restaurants = [ [1,4,1,40,10], [2,8,0,30,20], [3,8,1,30,30], [4,10,0,10,40], [5,1,1,15,25] ] veganFriendly = 1 maxPrice = 30 maxDistance = 3

Output:

[3,1,5]

Explanation:

Given that veganFriendly = 1, maxPrice = 30 and maxDistance = 3, the restaurants that meet these criteria are:

• Restaurant 1: veganFriendly = 1, price = 40, distance = 10, rating = 4.
• Restaurant 3: veganFriendly = 1, price = 30, distance = 30, rating = 8.
• Restaurant 5: veganFriendly = 1, price = 15, distance = 25, rating = 1.

The restaurants are sorted in descending order by their rating. Restaurants 1 and 3 have the same rating, but restaurant 3 has a smaller ID, so it comes before restaurant 1.

Solution

The approach for this problem is pretty straightforward. We need to loop through the given list of restaurants and filter the restaurants based on the given criteria. Then we can sort the filtered list based on the restaurant's rating and return a list of restaurant IDs in descending order.

Let's implement this approach step by step:

Step 1: Filter the restaurants based on the given criteria

We can loop through the list of restaurants and check if each restaurant meets the given criteria. If a restaurant meets all the criteria, we add it to a new list to keep track of the filtered restaurants.

def filterRestaurants(restaurants: List[List[int]], veganFriendly: int, maxPrice: int, maxDistance: int) -> List[int]: filteredRestaurants = [] for restaurant in restaurants: id, rating, isVegan, price, distance = restaurant

    # Check if the restaurant meets the given criteria
    if isVegan >= veganFriendly and price <= maxPrice and distance <= maxDistance:
        filteredRestaurants.append(restaurant)

return filteredRestaurants

Step 2: Sort the filtered restaurants based on their ratings

We can use the built-in sort function in Python to sort the filtered list of restaurants based on their rating. We need to sort the list in descending order by the rating, so we can pass a lambda function to the sort function to achieve this:

def filterRestaurants(restaurants: List[List[int]], veganFriendly: int, maxPrice: int, maxDistance: int) -> List[int]: filteredRestaurants = [] for restaurant in restaurants: id, rating, isVegan, price, distance = restaurant

    # Check if the restaurant meets the given criteria
    if isVegan >= veganFriendly and price <= maxPrice and distance <= maxDistance:
        filteredRestaurants.append(restaurant)

# Sort the filtered list in descending order by the rating
filteredRestaurants.sort(key=lambda x: (-x[1], x[0]))

return filteredRestaurants

Note that we also sort restaurants with the same rating in ascending order by their ID using x[0] in the second parameter of the lambda function.

Step 3: Return a list of restaurant IDs

Finally, we need to extract the restaurant IDs from the filtered and sorted list of restaurants and return them as a list:

def filterRestaurants(restaurants: List[List[int]], veganFriendly: int, maxPrice: int, maxDistance: int) -> List[int]: filteredRestaurants = [] for restaurant in restaurants: id, rating, isVegan, price, distance = restaurant

    # Check if the restaurant meets the given criteria
    if isVegan >= veganFriendly and price <= maxPrice and distance <= maxDistance:
        filteredRestaurants.append(restaurant)

# Sort the filtered list in descending order by the rating
filteredRestaurants.sort(key=lambda x: (-x[1], x[0]))

# Extract the restaurant IDs from the filtered list and return them as a list
return [restaurant[0] for restaurant in filteredRestaurants]

The final solution is given below:

def filterRestaurants(restaurants: List[List[int]], veganFriendly: int, maxPrice: int, maxDistance: int) -> List[int]: filteredRestaurants = [] for restaurant in restaurants: id, rating, isVegan, price, distance = restaurant

    # Check if the restaurant meets the given criteria
    if isVegan >= veganFriendly and price <= maxPrice and distance <= maxDistance:
        filteredRestaurants.append(restaurant)

# Sort the filtered list in descending order by the rating
filteredRestaurants.sort(key=lambda x: (-x[1], x[0]))

# Extract the restaurant IDs from the filtered list and return them as a list
return [restaurant[0] for restaurant in filteredRestaurants]

1