# Filter Restaurants by Vegan-Friendly, Price and Distance Leetcode Solution

Difficulty Level Medium
Frequently asked in Amazon YelpViews 24

## Problem Statement

Filter Restaurants by Vegan-Friendly, Price, and Distance Leetcode Solution – Given the array `restaurants` where  `restaurants[i] = [id`i`, rating`i`, veganFriendly`i`, price`i`, distance`i`]`. You have to filter the restaurants using three filters.

The `veganFriendly` filter will be either true (meaning you should only include restaurants with `veganFriendly`i set it to true) or false (meaning you can include any restaurant). In addition, you have the filters `maxPrice` and `maxDistance` which are the maximum value for price and distance of restaurants you should consider respectively.

Return the array of restaurant IDs after filtering, ordered by rating from highest to lowest. For restaurants with the same rating, order them by id from highest to lowest. For simplicity `veganFriendly`i and `veganFriendly` take value 1 when it is true, and 0 when it is false.

## Example

Input:

``` 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
```

Output:

``` [3,1,5]
```

Explanation:

```The restaurants are:
Restaurant 1 [id=1, rating=4, veganFriendly=1, price=40, distance=10]
Restaurant 2 [id=2, rating=8, veganFriendly=0, price=50, distance=5]
Restaurant 3 [id=3, rating=8, veganFriendly=1, price=30, distance=4]
Restaurant 4 [id=4, rating=10, veganFriendly=0, price=10, distance=3]
Restaurant 5 [id=5, rating=1, veganFriendly=1, price=15, distance=1]
After filter restaurants with veganFriendly = 1, maxPrice = 50 and maxDistance = 10 we have restaurant 3, restaurant 1 and restaurant 5 (ordered by rating from highest to lowest).```

Input:

``` 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 = 0, maxPrice = 50, maxDistance = 10
```

Output:

``` [4,3,2,1,5]
```

Explanation:

` The restaurants are the same as in example 1, but in this case the filter veganFriendly = 0, therefore all restaurants are considered.`

## Approach

### Idea:

The main idea is to first sort the list of restaurants by the ratings, if ratings are the same then by id. For this, we can build our own custom comparator function.

Now, that we have sorted the restaurants, we can insert the id’s of valid restaurants into another vector and return it.

## Code

### C++ Code for Filter Restaurants by Vegan-Friendly, Price and Distance

```class Solution {
public:
vector<int> filterRestaurants(vector<vector<int>>& restaurants, int veganFriendly, int maxPrice, int maxDistance) {
int n = restaurants.size();

//Firstly sort on the basis of the condition given.
sort(restaurants.begin(),restaurants.end(),[](vector<int> &a,vector<int> &b){
if(a[1] == b[1]){
return a[0] > b[0];
}
return a[1] > b[1];
});

vector<int> id;
//Then, insert the ids of valid restaurants in the result vector.
for(auto vc : restaurants){
if(veganFriendly==1 && vc[2]!=1){continue;}
if(vc[3]>maxPrice){continue;}
if(vc[4]>maxDistance){continue;}

id.push_back(vc[0]);
}

return id;
}
};```

### Java Code for Filter Restaurants by Vegan-Friendly, Price and Distance

```class Solution {
public List<Integer> filterRestaurants(int[][] restaurants, int veganFriendly, int maxPrice, int maxDistance) {
Arrays.sort(restaurants, (a,b) ->
(a[1]==b[1] ? b[0]-a[0] : b[1]-a[1])
);

List<Integer> result = new ArrayList<>();
for(int[] arr: restaurants) {
if((veganFriendly == arr[2] || veganFriendly == 0)
&& maxPrice >= arr[3] && maxDistance >= arr[4]) {
}
}

return result;
}
}```

## Complexity Analysis for Filter Restaurants by Vegan-Friendly, Price and Distance Leetcode Solution

### Time Complexity

Sorting the whole list takes O(nlogn) time and picking up the valid id from the sorted list takes another O(n) time, So the overall Complexity is O(n + nlogn) that is O(nlogn).

### Space Complexity

We are only using O(k) space, where k denotes the number of valid restaurants since in the worst case k can tend to n. So the overall Space Complexity is O(n).

Translate »