Filter Restaurants by Vegan-Friendly, Price and Distance

Problem Description

Given the array restaurants where restaurants[i] = [id_i, rating_i, veganFriendly_i, price_i, distance_i]. You have to filter the restaurants using three filters: veganFriendly, maxPrice, and maxDistance. Return the array of restaurant IDs after filtering, ordered by rating from highest to lowest, and by ID from highest to lowest for restaurants with the same rating.

Key Insights

• The veganFriendly filter can restrict the results based on whether the restaurant is vegan-friendly or not.
• The maxPrice and maxDistance filters help in narrowing down the options based on budget and proximity.
• Sorting the final results is crucial and involves multiple criteria: first by rating and then by ID.

Space and Time Complexity

Time Complexity: O(n log n) for sorting the filtered list, where n is the number of restaurants. Space Complexity: O(n) for storing the filtered results.

Solution

To solve the problem, we will:

1. Iterate over the list of restaurants and apply the filters based on the veganFriendly, maxPrice, and maxDistance criteria.
2. Collect the IDs of the filtered restaurants.
3. Sort the filtered list first by rating in descending order, then by ID in descending order for restaurants with the same rating.
4. Return the sorted list of IDs.

This requires using a list to hold the filtered results and a sorting algorithm to order them according to the specified criteria.

Code Solutions