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.
This approach involves iterating through each restaurant and checking if it fulfills the given conditions: vegan friendliness, price within the maximum limit, and distance within the maximum limit. After filtering, the resulting list of restaurants is sorted first by rating in descending order and then by ID in descending order.
In this solution, we first create a `Restaurant` structure to hold restaurant data. We iterate through all restaurants and check if they meet the filtering criteria: vegan-friendliness, price, and distance. We store qualifying restaurants in the `filtered` array.
After filtering, we use the C standard library function `qsort` to sort the resultant restaurants by rating and ID in the desired manner: by descending rating, followed by descending ID in case of ties.
Finally, we prepare the result array by storing IDs of the sorted restaurants and return the count of the filtered restaurants.
Time Complexity: O(n log n) due to sorting, where n is the number of restaurants. The initial filtering takes O(n).
Space Complexity: O(n), needed for storing filtered restaurants.
This approach makes use of a priority queue (often implemented as a min-heap) to filter and sort items efficiently. As we traverse through the list of restaurants, each is evaluated against criteria and added to the priority queue. When the heap size exceeds the needed capacity, the smallest element (in terms of our sorting requirements) is expelled, ensuring only the top items by our criteria remain.
This C++ solution leverages a priority queue with a custom comparator, which orders restaurants by descending rating and descending ID. By maintaining this order, the priority queue is able to dynamically manage the set of top items according to the specified criteria.
Iterating over all restaurants and adding those that meet the criteria, the priority queue will automatically maintain the current top entries. The IDs of these are then collected in the output list.
Time Complexity: O(n log k), where n is the number of restaurants and k is the size of the priority queue. In the worst case, k can be equivalent to n.
Space Complexity: O(n), needed for priority queue data storage.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Simple Filtering and Sorting | Time Complexity: O(n log n) due to sorting, where n is the number of restaurants. The initial filtering takes O(n). Space Complexity: O(n), needed for storing filtered restaurants. |
| Using Priority Queue (Heap) | Time Complexity: O(n log k), where n is the number of restaurants and k is the size of the priority queue. In the worst case, k can be equivalent to n. Space Complexity: O(n), needed for priority queue data storage. |
| Default Approach | — |
| 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. |
Leetcode 1333. Filter Restaurants by Vegan-Friendly, Price and Distance • Fraz • 13,234 views views
Watch 2 more video solutions →Practice Filter Restaurants by Vegan-Friendly, Price and Distance with our built-in code editor and test cases.
Practice on FleetCode