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.
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; }}Video 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.