{x}
blog image

Filter Restaurants by Vegan-Friendly, Price and Distance

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.

Solution Explanation

This problem involves filtering a list of restaurants based on vegan-friendliness, price, and distance, then sorting the results by rating and ID. The solution uses a straightforward approach combining filtering and sorting.

Algorithm:

  1. Sort: First, the restaurants array is sorted in descending order based on the rating (restaurants[i][1]). If two restaurants have the same rating, they are sorted in descending order by ID (restaurants[i][0]). This ensures that after filtering, the results are correctly ordered. Different languages use slightly different syntax for this sorting step (using lambda functions or custom comparator functions).

  2. Filter: Iterate through the sorted restaurants array. For each restaurant, check if it meets the specified criteria:

    • restaurants[i][2] >= veganFriendly: The restaurant's vegan-friendliness status meets the filter. Note that veganFriendly is 1 for true and 0 for false, allowing for flexible filtering.
    • restaurants[i][3] <= maxPrice: The restaurant's price is within the maximum price limit.
    • restaurants[i][4] <= maxDistance: The restaurant's distance is within the maximum distance limit.

  3. Append to Result: If all three conditions are true, the restaurant's ID (restaurants[i][0]) is added to the ans array.

  4. Return: Finally, the ans array (containing the filtered and sorted IDs) is returned.

Time Complexity: O(N log N)

The dominant operation is the sorting step, which has a time complexity of O(N log N), where N is the number of restaurants. The filtering and appending steps have a linear time complexity of O(N). Thus, the overall time complexity is dominated by the sorting, resulting in O(N log N).

Space Complexity: O(N) in the worst case

The space complexity is determined by the ans array which, in the worst case, could store all the restaurant IDs (if no filtering is applied). Thus, the space complexity is O(N). The space used for sorting might vary depending on the specific sorting algorithm used by the language's implementation, but it's generally considered to be O(log N) or O(1) for in-place sorting algorithms. Therefore, the overall space complexity is dominated by the output array leading to O(N).

Code in Different Languages:

The code examples provided in the original response demonstrate the algorithm in Python, Java, C++, Go, and TypeScript. Each implementation follows the same basic steps outlined in the algorithm description above, but uses the language's specific syntax for sorting and array manipulation. The key differences lie primarily in:

  • Sorting: Python uses a lambda function, Java and C++ use custom comparator functions, Go uses sort.Slice, and TypeScript leverages the sort method directly with a comparator.
  • Array Handling: The ways arrays are created, accessed, and iterated are language-specific. Note the use of list comprehensions in Python, for loops in Java, C++ range-based for loop and Go's range loop.

The provided code snippets are well-structured and efficiently implement the algorithm described above. They are also quite concise and readable for their respective languages.