1333. Filter Restaurants by Vegan-Friendly, Price and Distance LeetCode Solution
In this guide, you will get 1333. Filter Restaurants by Vegan-Friendly, Price and Distance LeetCode Solution with the best time and space complexity. The solution to Filter Restaurants by Vegan-Friendly, Price and Distance 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.
Problem Statement of Filter Restaurants by Vegan-Friendly, Price and Distance
Given the array restaurants where restaurants[i] = [idi, ratingi, veganFriendlyi, pricei, distancei]. You have to filter the restaurants using three filters.
The veganFriendly filter will be either true (meaning you should only include restaurants with veganFriendlyi set 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 veganFriendlyi and veganFriendly take value 1 when it is true, and 0 when it is false.
Example 1:
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.
1 <= restaurants.length <= 10^4
restaurants[i].length == 5
1 <= idi, ratingi, pricei, distancei <= 10^5
1 <= maxPrice, maxDistance <= 10^5
veganFriendlyi and veganFriendly are 0 or 1.
All idi are distinct.
Complexity Analysis
Time Complexity: O(n^3)
Space Complexity: O(n^2)
1333. Filter Restaurants by Vegan-Friendly, Price and Distance LeetCode Solution in C++
class Solution {
public:
vector<int> filterRestaurants(vector<vector<int>>& restaurants,
int veganFriendly, int maxPrice,
int maxDistance) {
vector<int> ans;
vector<vector<int>> filtered;
for (vector<int>& restaurant : restaurants)
if (restaurant[2] >= veganFriendly && restaurant[3] <= maxPrice &&
restaurant[4] <= maxDistance)
filtered.push_back(restaurant);
ranges::sort(filtered, [](const vector<int>& a, const vector<int>& b) {
return a[1] == b[1] ? a[0] > b[0] : a[1] > b[1];
});
for (const vector<int>& f : filtered)
ans.push_back(f[0]);
return ans;
}
}; /* code provided by PROGIEZ */
1333. Filter Restaurants by Vegan-Friendly, Price and Distance LeetCode Solution in Java
class Solution {
public List<Integer> filterRestaurants(int[][] restaurants, int veganFriendly, int maxPrice,
int maxDistance) {
return Arrays.stream(restaurants)
.filter(r -> r[2] >= veganFriendly && r[3] <= maxPrice && r[4] <= maxDistance)
.sorted((a, b) -> a[1] == b[1] ? Integer.compare(b[0], a[0]) : Integer.compare(b[1], a[1]))
.map(i -> i[0])
.collect(Collectors.toList());
}
} // code provided by PROGIEZ
1333. Filter Restaurants by Vegan-Friendly, Price and Distance LeetCode Solution in Python
class Solution:
def filterRestaurants(
self,
restaurants: list[list[int]],
veganFriendly: int,
maxPrice: int,
maxDistance: int,
) -> list[int]:
restaurants.sort(key=lambda x: (-x[1], -x[0]))
return [i for i, _, v, p, d in restaurants
if v >= veganFriendly and p <= maxPrice and d <= maxDistance] # code by PROGIEZ
