We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Filter Restaurants by Vegan-Friendly, Price and Distance

Number: 1455

Difficulty: Medium

Paid? No

Companies: Yelp

Problem Description

Given an array of restaurants where each restaurant is represented as [id, rating, veganFriendly, price, distance], filter the restaurants based on three criteria: vegan-friendly flag, maximum price, and maximum distance. After filtering, return the list of restaurant IDs sorted by rating in descending order, and for restaurants with the same rating, sort by id in descending order.

Key Insights

  • Filter restaurants using the veganFriendly flag (if set to 1, only include those with a veganFriendly flag of 1).
  • Use the maxPrice and maxDistance to limit the selection.
  • After filtering, sort the results first by rating (highest to lowest) and then by id (highest to lowest) when ratings are identical.
  • Iterating over the list for filtering and then sorting leads to a time complexity of O(n log n).

Space and Time Complexity

Time Complexity: O(n log n) – Filtering takes O(n) and sorting takes O(n log n). Space Complexity: O(n) – In worst-case scenario, all restaurants meet the filter criteria.

Solution

To solve the problem, first traverse the list of restaurants and select only those restaurants that meet the criteria:

  1. If veganFriendly is set to 1, only restaurants with a veganFriendly value of 1 are accepted.
  2. The restaurant's price should be less than or equal to maxPrice.
  3. The restaurant's distance should be less than or equal to maxDistance. After filtering, sort the remaining restaurants by rating (in descending order) and then by id (in descending order in case of a tie in ratings). Finally, extract the id from each sorted restaurant and return the resulting list.

Code Solutions

# Define the function to filter restaurants.
def filterRestaurants(restaurants, veganFriendly, maxPrice, maxDistance):
    # Filter the restaurants based on the given conditions.
    filtered = []
    for rest in restaurants:
        # rest: [id, rating, veganFriendly, price, distance]
        # If veganFriendly filter is set, check the restaurant's veganFriendly flag.
        if veganFriendly == 1 and rest[2] != 1:
            continue
        # Check if restaurant meets price and distance criteria.
        if rest[3] > maxPrice or rest[4] > maxDistance:
            continue
        filtered.append(rest)
    
    # Sort filtered restaurants by rating in descending order.
    # If ratings are equal, sort by id in descending order.
    filtered.sort(key=lambda x: (x[1], x[0]), reverse=True)
    
    # Extract the restaurant ids from the sorted list.
    return [rest[0] for rest in filtered]

# Example usage:
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]]
print(filterRestaurants(restaurants, 1, 50, 10))
← Back to All Questions