Leetcode 1333: Filter Restaurants by Vegan-Friendly, Price and Distance
You are given a list of restaurants where each restaurant is represented by an array: [id, rating, veganFriendly, price, distance]. Filter these restaurants based on three criteria: vegan friendliness, maximum price, and maximum distance. Return the restaurant IDs, ordered by rating (highest first), and by ID (highest first) when ratings are tied.
Problem
Approach
Steps
Complexity
Input: The input consists of a list of lists where each inner list represents a restaurant. The structure of each inner list is [id, rating, veganFriendly, price, distance]. Three additional parameters are provided: veganFriendly (1 or 0), maxPrice, and maxDistance.
Example: [[1,5,1,40,10], [2,8,0,50,5], [3,7,1,20,3], [4,9,0,15,6], [5,2,1,25,7]]
Constraints:
• 1 <= restaurants.length <= 10^4
• restaurants[i].length == 5
• 1 <= id, rating, price, distance <= 10^5
• 1 <= maxPrice, maxDistance <= 10^5
• veganFriendly is 0 or 1
• All ids are distinct.
Output: The output is a list of restaurant IDs after applying the filters, sorted by rating in descending order and by ID in descending order for restaurants with the same rating.
Example: [4,2,3,1,5]
Constraints:
Goal: The goal is to filter the restaurants based on vegan friendliness, maximum price, and maximum distance. Then, sort the remaining restaurants by rating and ID.
Steps:
• Loop through each restaurant and apply the filters based on veganFriendly, maxPrice, and maxDistance.
• After filtering, sort the remaining restaurants based on their rating (highest to lowest) and ID (highest to lowest).
Goal:
Steps:
Assumptions:
• Restaurants with the same rating should be sorted by their ID.
• All restaurant IDs are unique.
• Input: [[1,5,1,40,10], [2,8,0,50,5], [3,7,1,20,3], [4,9,0,15,6], [5,2,1,25,7]]
• Explanation: This example demonstrates filtering based on vegan friendliness and maximum price and distance. After filtering, restaurants are sorted by rating (highest first) and ID (highest first).
Approach: To solve this problem, we need to filter and sort the restaurants based on the given criteria.
Observations:
• Restaurants need to be filtered before sorting.
• Sorting should be done based on two criteria: rating and ID.
• The best approach is to first filter the restaurants and then sort them according to the rating and ID.
Steps:
• 1. Loop through the restaurants and apply the veganFriendly, maxPrice, and maxDistance filters.
• 2. Sort the filtered restaurants by rating in descending order. If two ratings are the same, sort by ID in descending order.
• 3. Return the list of IDs from the sorted restaurants.
Empty Inputs:
• If there are no restaurants after applying filters, the output should be an empty list.
Large Inputs:
• The solution should be efficient enough to handle large inputs (up to 10^4 restaurants).
Special Values:
• All restaurants being excluded due to filters.
Constraints:
• Restaurants' IDs are distinct.
static bool cmp(vector<int> &a, vector<int> &b) {
if(a[1] == b[1]) return a[0] > b[0];
else return a[1] > b[1];
}
vector<int> filterRestaurants(vector<vector<int>>& rest, int veg, int mxp, int mxd) {
vector<vector<int>> ans;
for(auto r: rest) {
if((!veg || (veg == r[2])) && r[3] <= mxp && r[4] <= mxd) {
ans.push_back({r[0], r[1]});
}
}
sort(ans.begin(), ans.end(), cmp);
vector<int> res;
for(auto x: ans) {
res.push_back(x[0]);
}
return res;
}
1 : Comparator Function
static bool cmp(vector<int> &a, vector<int> &b) {
This defines a comparator function 'cmp' which is used to sort restaurants. It compares two restaurants based on their ratings, and in case of a tie, it compares by restaurant ID.
2 : Comparator - Rating Tie
if(a[1] == b[1]) return a[0] > b[0];
If the ratings are equal, the function compares the restaurant IDs, and returns true if the ID of 'a' is greater than that of 'b'.
3 : Comparator - Rating Comparison
else return a[1] > b[1];
If the ratings are not equal, the function compares them and returns true if 'a' has a higher rating than 'b'.
4 : Function Declaration
vector<int> filterRestaurants(vector<vector<int>>& rest, int veg, int mxp, int mxd) {
The 'filterRestaurants' function is declared, which takes the list of restaurants and three integer parameters (veg, mxp, mxd) as inputs. It returns a vector of restaurant IDs.
5 : Initialize Answer List
vector<vector<int>> ans;
A 2D vector 'ans' is initialized to store the filtered restaurants' IDs and ratings.
6 : Loop Over Restaurants
for(auto r: rest) {
The function begins looping over each restaurant in the input list 'rest'.
7 : Filter Condition
if((!veg || (veg == r[2])) && r[3] <= mxp && r[4] <= mxd) {
This condition filters restaurants based on whether they are vegetarian (if 'veg' is true), and if their price and distance meet the given thresholds ('mxp' and 'mxd').
8 : Add to Answer List
ans.push_back({r[0], r[1]});
If the restaurant satisfies the filtering conditions, its ID and rating are added to the 'ans' vector.
9 : Sort the Filtered List
sort(ans.begin(), ans.end(), cmp);
The filtered list of restaurants is sorted using the 'cmp' comparator function defined earlier.
10 : Initialize Result List
vector<int> res;
A vector 'res' is initialized to store the final result, which will be the restaurant IDs after sorting.
11 : Populate Result List
for(auto x: ans) {
This loop goes through the sorted list 'ans' and extracts the restaurant IDs to store them in the 'res' vector.
12 : Add ID to Result
res.push_back(x[0]);
The restaurant ID 'x[0]' is added to the 'res' vector.
13 : Return the Result
return res;
The function returns the final sorted and filtered list of restaurant IDs.
Best Case: O(n log n) where n is the number of restaurants.
Average Case: O(n log n) due to the sorting step.
Worst Case: O(n log n) due to the sorting step.
Description: The main time complexity comes from sorting the restaurants.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) for storing the filtered restaurants before sorting.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus