Leetcode 1333. Filter Restaurants by Vegan-Friendly, Price and Distance

Problem Explanation:

The problem is about filtering restaurants based on a few criteria and then sorting them according to their ratings and IDs. Initially, we are given a list of restaurants where each restaurant is represented as a list with elements [id, rating, veganFriendly, price, distance]. Here, id is the identification number of the restaurant, rating is the rating of the restaurant, veganFriendly is a boolean value indicating whether the restaurant is vegan-friendly or not, price is the price of the items at the restaurant, and distance is the distance to the restaurant from a particular location.

We need to filter the restaurants based on three input parameters: veganFriendly, maxPrice, and maxDistance. veganFriendly is a boolean value, if it's true, we include only those restaurants which are vegan-friendly, if it's false, we include all restaurants. maxPrice and maxDistance are maximum limits for the price and the distance of the restaurants that we should consider.

After these filters, all the remaining restaurants are sorted by their ratings in descending order. If multiple restaurants have the same rating, they should be sorted by their ids in descending order. Finally, we return a list of filtered and sorted restaurant ids.

For example, let's consider the input from the first example in the problem:

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

After applying the filters for veganFriendly, maxPrice, and maxDistance, we get the following remaining restaurants:

Restaurant 1 [id=1, rating=4, veganFriendly=1, price=40, distance=10] Restaurant 3 [id=3, rating=8, veganFriendly=1, price=30, distance=4] Restaurant 5 [id=5, rating=1, veganFriendly=1, price=15, distance=1]

Now we sort these restaurants by rating in descending order and by id in descending order for the same ratings:

Restaurant 3 [id=3, rating=8, veganFriendly=1, price=30, distance=4] Restaurant 1 [id=1, rating=4, veganFriendly=1, price=40, distance=10] Restaurant 5 [id=5, rating=1, veganFriendly=1, price=15, distance=1]

Hence, the output would be [3, 1, 5] which are the ids of the filtered and sorted restaurants.

Approach:

1. First, we create an empty list to store the filtered restaurants.

2. Then we iterate over the given list of restaurants. For each restaurant, we check if it satisfies all the filter conditions. If it does, we add it to the list of filtered restaurants.

3. After getting the filtered restaurants, we sort this list. The sort order is first by rating in descending order and then by id in descending order for the same ratings.

4. Finally, we create a list of ids of the sorted restaurants and return it.

This problem can be solved using a simple filtering and sorting approach.

Python Solution:

1
2python
3class Solution:
4    def filterRestaurants(self, restaurants: List[List[int]], veganFriendly: int, maxPrice: int, maxDistance: int) -> List[int]:
5
6        # Filter the restaurants based on the provided conditions
7        filtered_restaurants = [
8            r for r in restaurants 
9            if r[2] >= veganFriendly and r[3] <= maxPrice and r[4] <= maxDistance
10        ]
11
12        # Sort the filtered restaurants first by rating and then by id, both in descending order
13        filtered_restaurants.sort(key=lambda r: (-r[1], -r[0]))
14        
15        # Return the ids of the sorted restaurants
16        return [r[0] for r in filtered_restaurants]

In the above solution, we first filter the restaurants using a list comprehension which checks each restaurant against the provided conditions. Then we sort the filtered restaurants using the sort function of python with a custom key function which returns a tuple of rating and id of the restaurant, both negated for descending sort. Finally, we return a list of the ids of the filtered and sorted restaurants using another list comprehension.JavaScript Solution:

The JavaScript solution also follows a similar approach as python. JavaScript has a filter() function for arrays which is very convenient for applying the filter conditions. For sorting, JavaScript also provides a sort() function with a comparison function.

1
2javascript
3var filterRestaurants = function(restaurants, veganFriendly, maxPrice, maxDistance) {
4    // Filter the restaurants based on the provided conditions
5    let filtered_restaurants = restaurants.filter(r =>
6        r[2] >= veganFriendly && r[3] <= maxPrice && r[4] <= maxDistance
7    );
8
9    // Sort the filtered restaurants first by rating and then by id, both in descending order
10    filtered_restaurants.sort((a, b) =>
11        b[1] - a[1] || b[0] - a[0]
12    );
13    
14    // Return the ids of the sorted restaurants
15    return filtered_restaurants.map(r => r[0]);
16};

In the JavaScript solution, we use the filter() function with a condition callback to filter the restaurants. For sorting, we use the sort() function with a custom comparison function which subtracts the ratings and ids (for same ratings) of two restaurants. Finally, we use the map() function to create and return a list of the ids of the filtered and sorted restaurants.

Java Solution:

Java provides a stream API for collections which we can use for filtering and sorting the restaurants.

1
2java
3import java.util.*;
4public class Solution {
5    public List<Integer> filterRestaurants(int[][] restaurants, int veganFriendly, int maxPrice, int maxDistance) {
6        // Filter the restaurants based on the provided conditions and sort them
7        return Arrays.stream(restaurants)
8            .filter(r -> r[2] >= veganFriendly && r[3] <= maxPrice && r[4] <= maxDistance)
9            .sorted((r1, r2) -> r1[1] == r2[1] ? r2[0] - r1[0] : r2[1] - r1[1])
10            .map(r -> r[0])
11            .collect(Collectors.toList());
12    }
13}

In the Java solution, we first convert the 2D array of restaurants into a stream using Arrays.stream(). Then we use the filter() method with a condition lambda to filter the restaurants. For sorting, we use the sorted() method with a comparator lambda which compares the ratings and ids (for same ratings) of two restaurants. Finally, we use the map() method to convert each restaurant into its id and then collect these ids into a list using Collectors.toList(). We return this list of ids as the result.

In all the three solutions, we use the functional programming features of the respective languages to concisely solve the problem using a very clear and understandable approach.