Filter Restaurants by Vegan-Friendly, Price and Distance
MedPrompt
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). Example 2:
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.Example 3:
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 = 30, maxDistance = 3
Output: [4,5]
Constraints:
1 <= restaurants.length <= 10^4restaurants[i].length == 51 <= idi, ratingi, pricei, distancei <= 10^51 <= maxPrice, maxDistance <= 10^5veganFriendlyiandveganFriendlyare 0 or 1.- All
idiare distinct.
Approaches
3 approaches with complexity analysis and trade-offs.
This straightforward but less efficient approach involves sorting the entire list of restaurants first, based on the required criteria (rating and ID). After sorting, it iterates through the now-ordered list and filters out restaurants that do not meet the given conditions (veganFriendly, maxPrice, maxDistance).
Algorithm
- Define a custom
Comparatorto sort restaurants by rating (descending) and then ID (descending). - Sort the entire
restaurantsarray using this comparator. - Initialize an empty list,
result, to store the final restaurant IDs. - Iterate through each
restaurantin the sortedrestaurantsarray. - For each restaurant, check if it satisfies the
veganFriendly,maxPrice, andmaxDistanceconstraints. - If all conditions are met, add the restaurant's ID (
restaurant[0]) to theresultlist. - Return the
resultlist.
Walkthrough
The main idea is to establish the final desired order for all restaurants before checking if they are valid candidates. A custom Comparator is used to sort the restaurants array. The comparator prioritizes higher ratings, and for ties in rating, it prioritizes higher IDs. Once the entire array is sorted, a single pass is performed to check each restaurant against the three filters. Restaurants that pass all filters are added to a result list. Since the main array was already sorted, the restaurants are added to the result list in the correct final order, preserving the sort.
import java.util.ArrayList;import java.util.Arrays;import java.util.List; class Solution { public List<Integer> filterRestaurants(int[][] restaurants, int veganFriendly, int maxPrice, int maxDistance) { // 1. Sort the entire array first Arrays.sort(restaurants, (a, b) -> { if (a[1] != b[1]) { return Integer.compare(b[1], a[1]); // Sort by rating descending } else { return Integer.compare(b[0], a[0]); // Sort by ID descending } }); List<Integer> result = new ArrayList<>(); // 2. Iterate and filter for (int[] r : restaurants) { // The veganFriendly filter applies only if veganFriendly is 1. if (veganFriendly == 1 && r[2] == 0) { continue; } if (r[3] <= maxPrice && r[4] <= maxDistance) { result.add(r[0]); } } return result; }}Complexity
Time
O(N log N), where N is the number of restaurants. Sorting the entire array is the dominant operation.
Space
O(N) in the worst case. This is for the space required by the sorting algorithm (e.g., TimSort's worst-case space) and the result list, where N is the total number of restaurants.
Trade-offs
Pros
Conceptually simple to understand: sort everything, then pick what you need.
Cons
Inefficient as it performs a costly sort operation on all N restaurants, including those that will be filtered out. This is particularly wasteful if the filters are very restrictive.
A more efficient approach is to first filter the restaurants and then sort only the ones that meet the criteria. This avoids the overhead of sorting elements that will be discarded.
Algorithm
- Initialize an empty list,
filteredRestaurants. - Iterate through the input
restaurantsarray. - For each restaurant, if it satisfies the
veganFriendly,maxPrice, andmaxDistancefilters, add it tofilteredRestaurants. - Sort the
filteredRestaurantslist using a customComparator(rating descending, then ID descending). - Initialize an empty list,
resultIds. - Iterate through the sorted
filteredRestaurantsand add each restaurant's ID toresultIds. - Return
resultIds.
Walkthrough
This method involves two main passes. In the first pass, we iterate through the original restaurants array. Each restaurant is checked against the veganFriendly, maxPrice, and maxDistance filters. If a restaurant passes all checks, it is added to a temporary list. After this filtering pass, the temporary list contains only the valid restaurants. In the second step, we sort this (potentially much smaller) temporary list using the same custom comparator as before (rating descending, then ID descending). Finally, we create the result list by extracting the IDs from the sorted temporary list.
import java.util.ArrayList;import java.util.Collections;import java.util.List; class Solution { public List<Integer> filterRestaurants(int[][] restaurants, int veganFriendly, int maxPrice, int maxDistance) { List<int[]> filtered = new ArrayList<>(); // 1. Filter the restaurants for (int[] r : restaurants) { if (veganFriendly == 1 && r[2] == 0) { continue; } if (r[3] <= maxPrice && r[4] <= maxDistance) { filtered.add(r); } } // 2. Sort the filtered list Collections.sort(filtered, (a, b) -> { if (a[1] != b[1]) { return Integer.compare(b[1], a[1]); // Sort by rating descending } else { return Integer.compare(b[0], a[0]); // Sort by ID descending } }); // 3. Extract IDs List<Integer> result = new ArrayList<>(); for (int[] r : filtered) { result.add(r[0]); } return result; }}Complexity
Time
O(N + K log K), where N is the total number of restaurants and K is the number of restaurants that pass the filters. O(N) for filtering and O(K log K) for sorting. This is significantly better than O(N log N) when K is small.
Space
O(K) to store the filtered list of restaurants, where K is the number of filtered restaurants. In the worst case, K=N, and the complexity becomes O(N).
Trade-offs
Pros
More efficient than the 'Sort then Filter' approach, especially when filters are strict.
Avoids unnecessary sorting operations on irrelevant data.
Cons
Requires extra space (O(K)) to store the filtered list before sorting.
This approach uses the modern Java Stream API to achieve the same 'Filter then Sort' logic in a more concise and declarative way. It chains filtering and sorting operations into a single, readable pipeline.
Algorithm
- Create a stream from the
restaurantsarray. - Chain a
filter()operation to the stream to select restaurants based on the three criteria. - Chain a
sorted()operation with a customComparatorto sort the filtered stream by rating (desc) and then ID (desc). - Chain a
map()operation to extract the ID from each restaurant object. - Use
collect(Collectors.toList())to terminate the stream and gather the results into a list. - Return the resulting list.
Walkthrough
This is the most idiomatic way to solve the problem in modern Java. We create a stream from the restaurants array. The filter() operation is used to apply the veganFriendly, maxPrice, and maxDistance conditions. Because streams are lazy, these filters are applied efficiently. The sorted() operation is then called on the resulting stream of filtered restaurants, using a comparator to sort by rating (desc) and then ID (desc). The map() operation transforms the stream of sorted restaurant arrays into a stream of their IDs. Finally, the collect() terminal operation gathers the IDs into a list.
import java.util.Arrays;import java.util.List;import java.util.stream.Collectors; class Solution { public List<Integer> filterRestaurants(int[][] restaurants, int veganFriendly, int maxPrice, int maxDistance) { return Arrays.stream(restaurants) .filter(r -> (veganFriendly == 0 || r[2] == 1) && r[3] <= maxPrice && r[4] <= maxDistance) .sorted((a, b) -> { if (a[1] != b[1]) { return Integer.compare(b[1], a[1]); } else { return Integer.compare(b[0], a[0]); } }) .map(r -> r[0]) .collect(Collectors.toList()); }}Complexity
Time
O(N + K log K), where N is the total number of restaurants and K is the number of filtered restaurants. The performance is identical to the manual 'Filter then Sort' approach.
Space
O(K) to store the filtered elements for sorting and the final result, where K is the number of filtered restaurants. In the worst case, this is O(N).
Trade-offs
Pros
Highly readable and concise, expressing intent clearly.
Functionally equivalent to the optimal manual approach.
Leverages modern Java features for cleaner code.
Cons
May have a slight performance overhead compared to manual loops due to stream object creation, though this is usually negligible.
Can be less intuitive for developers not yet comfortable with functional programming and streams.
Solutions
Solution
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> ans = new ArrayList<>(); for (int[] r : restaurants) { if (r[2] >= veganFriendly && r[3] <= maxPrice && r[4] <= maxDistance) { ans.add(r[0]); } } return ans; }}class Solution {public: vector<int> filterRestaurants(vector<vector<int>> &restaurants, int veganFriendly, int maxPrice, int maxDistance) { sort(restaurants.begin(), restaurants.end(), [](const vector<int> &a, const vector<int> &b) { if (a[1] != b[1]) { return a[1] > b[1]; } return a[0] > b[0]; }); vector<int> ans; for (auto &r : restaurants) { if (r[2] >= veganFriendly && r[3] <= maxPrice && r[4] <= maxDistance) { ans.push_back(r[0]); } } return ans; }};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])) ans = [] for idx, _, vegan, price, dist in restaurants: if vegan >= veganFriendly and price <= maxPrice and dist <= maxDistance: ans . append(idx) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.