#1333

Medium

LeetCode Problem Workspace

Filter Restaurants by Vegan-Friendly, Price and Distance

Filter restaurants by vegan-friendly status, price, and distance, and sort them by rating and ID.

Problem Statement

You are given an array of restaurants, where each restaurant is represented as [id, rating, veganFriendly, price, distance]. Your task is to filter the restaurants based on three parameters: vegan-friendly status, maximum price, and maximum distance. The vegan-friendly filter is either true (1) or false (0), which dictates whether only vegan-friendly restaurants should be included. Additionally, maxPrice and maxDistance are the maximum price and distance you are willing to accept for a restaurant.

After filtering the restaurants, you need to return their IDs sorted first by rating in descending order and then by ID in descending order for restaurants with the same rating. For simplicity, treat vegan-friendly values as 1 for true and 0 for false. You should consider all restaurants where the values for price and distance meet your criteria.

Examples

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]

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]

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]

Example details omitted.

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 Approach

Filter Restaurants Based on Criteria

Start by applying the vegan-friendly, maxPrice, and maxDistance filters. Loop through the array and only keep restaurants that meet all three criteria. If vegan-friendly is 1, ensure the restaurant's vegan-friendly value is also 1. Similarly, ensure the price is less than or equal to maxPrice and the distance is less than or equal to maxDistance.

Sorting Restaurants

After filtering, you need to sort the remaining restaurants by their ratings in descending order. If two restaurants have the same rating, sort them by their ID in descending order. This can be achieved by a custom sort function that handles these two criteria.

Return Sorted IDs

Once the restaurants are sorted, extract their IDs and return the list of IDs in the required order. This step involves transforming the sorted list into a list of IDs, which is the final result.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this solution depends on the filtering and sorting steps. Filtering the array takes O(n), where n is the number of restaurants. Sorting the filtered restaurants takes O(m log m), where m is the number of restaurants that pass the filter. Thus, the overall time complexity is O(n + m log m). Space complexity is O(n) for storing the filtered list and the sorted results.

What Interviewers Usually Probe

The candidate is expected to understand how to filter an array based on multiple criteria.
The sorting of the filtered array should be done using custom sorting with multiple conditions.
The candidate should explain how they would handle edge cases, such as no restaurants meeting the criteria.

Common Pitfalls or Variants

Common pitfalls

Failing to correctly apply the vegan-friendly filter, resulting in incorrect results for restaurants with 0 or 1 values.
Not handling the sorting correctly, such as failing to break ties based on the restaurant ID in case of equal ratings.
Not considering edge cases where no restaurants pass the filter, which should return an empty list.

Follow-up variants

Consider different variations where only one of the filters (vegan-friendly, maxPrice, or maxDistance) is applied.
Handle cases where multiple restaurants have identical ratings and IDs, ensuring the correct sorting and filtering behavior.
Modify the problem to return the full restaurant details (instead of just IDs) after filtering and sorting.

FAQ

How do I filter restaurants by vegan-friendly status, price, and distance?

You need to apply filters for vegan-friendly (true or false), price, and distance, keeping only those restaurants that satisfy all the given conditions.

What happens if two restaurants have the same rating?

If two restaurants have the same rating, they should be sorted by their IDs in descending order to break the tie.

What is the expected output format of this problem?

The expected output is a list of restaurant IDs, sorted by rating first and then by ID for restaurants with equal ratings.

Can the restaurant IDs be the same as the array index?

No, the restaurant IDs are independent of their positions in the array and can be any distinct integer value.

How does GhostInterview help with this problem?

GhostInterview helps by offering tailored hints and explanations, allowing you to improve your understanding of array filtering and sorting in this specific problem.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def filterRestaurants(
        self,
        restaurants: List[List[int]],
        veganFriendly: int,
        maxPrice: int,
        maxDistance: int,
    ) -> List[int]:
        restaurants.sort(key=lambda x: (-x[1], -x[0]))
        ans = []
        for idx, _, vegan, price, dist in restaurants:
            if vegan >= veganFriendly and price <= maxPrice and dist <= maxDistance:
                ans.append(idx)
        return ans

Continue Practicing

#1331 rank transform of an array #1329 sort the matrix diagonally #1337 the k weakest rows in a matrix