Skip to main content
Talentd

Filter Restaurants by Vegan-Friendly, Price and Distance - Solution & Explanation

MediumArraySorting13 min readAsked at: Yelp
Practice this problem

Problem Statement

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^4
  • restaurants[i].length == 5
  • 1 <= idi, ratingi, pricei, distancei <= 10^5
  • 1 <= maxPrice, maxDistance <= 10^5
  • veganFriendlyi and veganFriendly are 0 or 1.
  • All idi are distinct.

Approach Overview

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 1: Simple Filtering and Sorting

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Using Priority Queue (Heap)

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.

Code

C++Java

C++

Java

Complexity

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.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Simple Filtering and SortingO(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.

Video Solution

Leetcode 1333. Filter Restaurants by Vegan-Friendly, Price and Distance • Fraz • 13,329 views views

Watch 3 more video solutions →

Frequently Asked Questions

Is Filter Restaurants by Vegan-Friendly, Price and Distance easy or hard?
The problem is rated Medium because it requires combining conditional filtering with multi-criteria sorting. The algorithm itself is straightforward, but candidates must correctly apply the constraints and comparator ordering.
Filter Restaurants by Vegan-Friendly, Price and Distance Python/Java solution
In Python, filter the list using a list comprehension and sort with a custom key like (-rating, -id). In Java, iterate through the array, store valid restaurants in a list, and call Collections.sort with a comparator that orders by rating descending then id descending.
How to solve Filter Restaurants by Vegan-Friendly, Price and Distance in O(n)?
A strict O(n) solution is not practical because the final output must be ordered by rating and id. Any comparison-based ordering requires sorting or heap operations, leading to O(n log n) time in the general case. Filtering alone is O(n), but ordering introduces the log n factor.
What is the best approach for Filter Restaurants by Vegan-Friendly, Price and Distance?
The most practical solution filters restaurants using the given constraints and then sorts the remaining entries by rating and id in descending order. Filtering takes O(n) time and sorting takes O(n log n), which dominates the runtime. This approach is concise and directly maps to the problem requirements.
Is Filter Restaurants by Vegan-Friendly, Price and Distance asked at Google/Amazon/Meta?
Problems combining filtering with custom sorting appear frequently in interviews at companies like Amazon, Google, and Meta. Interviewers use them to evaluate how you process arrays, apply constraints, and implement multi-key sorting logic.
What data structure is used in Filter Restaurants by Vegan-Friendly, Price and Distance?
The primary data structures are arrays or lists to store the restaurants and the filtered results. Sorting utilities with custom comparators are used to order the results. An alternative solution uses a priority queue (max-heap) to retrieve restaurants by rating and id order.
What is the time complexity of Filter Restaurants by Vegan-Friendly, Price and Distance?
The typical solution runs in O(n log n) time. You first scan the array once to filter valid restaurants in O(n), then sort the filtered results by rating and id which costs O(n log n). Space complexity is O(n) to store the filtered list.

Ready to solve this problem?

Practice Filter Restaurants by Vegan-Friendly, Price and Distance with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays