Watch 3 video solutions for Filter Restaurants by Vegan-Friendly, Price and Distance, a medium level problem involving Array, Sorting. This walkthrough by Fraz has 13,234 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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^5veganFriendlyi and veganFriendly are 0 or 1.idi are distinct.Problem Overview: You receive a list of restaurants where each entry contains id, rating, veganFriendly, price, and distance. Your task is to filter restaurants based on vegan preference, maximum price, and maximum distance, then return the remaining restaurant IDs sorted by rating (descending) and id (descending).
Approach 1: Simple Filtering and Sorting (O(n log n) time, O(n) space)
Scan the input array and filter out restaurants that do not satisfy the constraints. If veganFriendly = 1, only keep restaurants with the vegan flag set. Also discard any restaurant where price > maxPrice or distance > maxDistance. Store the valid restaurants in a temporary list.
Next, sort this filtered list by two keys: rating in descending order and id in descending order. Most languages support custom comparators or tuple-based sorting, which makes this step straightforward. After sorting, iterate through the list and collect only the restaurant IDs.
This approach works well because filtering is linear and sorting dominates the runtime at O(n log n). The implementation is short and easy to reason about, making it the most common solution for problems involving array processing combined with sorting.
Approach 2: Using Priority Queue (Heap) (O(n log n) time, O(n) space)
Instead of sorting the entire filtered list at the end, push valid restaurants into a max-heap ordered by rating first and id second. While iterating through the restaurants, apply the same filtering conditions and insert qualifying entries into the heap.
Once all valid restaurants are in the heap, repeatedly pop the top element to retrieve restaurants in the correct order. Each insertion and removal costs O(log n), so building and draining the heap leads to O(n log n) time overall. This method highlights the use of a heap when ordered extraction is required.
Recommended for interviews: The filtering + sorting approach is what most interviewers expect. It demonstrates that you can apply constraints with a linear scan and then use a custom comparator to enforce multi-key ordering. The heap solution is also valid but adds unnecessary complexity unless the problem specifically requires incremental retrieval.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simple Filtering and Sorting | O(n log n) | O(n) | Best general solution when you can filter first and then sort by multiple fields. |
| Priority Queue (Heap) | O(n log n) | O(n) | Useful when you need ordered extraction or streaming results instead of sorting once. |