Problem Description

You are given an array of restaurants where each restaurant is represented as restaurants[i] = [id_i, rating_i, veganFriendly_i, price_i, distance_i]. Each restaurant has:

• id_i: unique identifier for the restaurant
• rating_i: rating of the restaurant
• veganFriendly_i: 1 if the restaurant is vegan-friendly, 0 otherwise
• price_i: price level of the restaurant
• distance_i: distance to the restaurant

You need to filter the restaurants based on three criteria:

1. veganFriendly filter: If set to 1 (true), only include restaurants where veganFriendly_i = 1. If set to 0 (false), include all restaurants regardless of their vegan-friendly status.
2. maxPrice filter: Only include restaurants where price_i <= maxPrice
3. maxDistance filter: Only include restaurants where distance_i <= maxDistance

After filtering, return an array containing only the IDs of the qualifying restaurants, sorted by:

• Primary sort: Rating in descending order (highest rating first)
• Secondary sort: For restaurants with the same rating, sort by ID in descending order (highest ID first)

The solution approach sorts all restaurants by rating and ID in descending order first. Then it iterates through the sorted list, checking each restaurant against the three filter conditions. If a restaurant passes all filters (vegan status meets or exceeds the requirement, price is within limit, and distance is within limit), its ID is added to the result list. The key insight is that vegan >= veganFriendly handles both cases: when veganFriendly = 1, only vegan restaurants (with value 1) pass; when veganFriendly = 0, all restaurants pass since both 0 and 1 are >= 0.

Intuition

The problem asks us to filter restaurants based on certain criteria and then return their IDs in a specific order. The natural approach is to think about this in two steps: filtering and sorting.

For the filtering part, we need to check three conditions for each restaurant. The tricky part is the vegan-friendly filter. When veganFriendly = 1, we only want vegan restaurants. When veganFriendly = 0, we want all restaurants. Instead of writing an if-else statement, we can use a clever comparison: vegan >= veganFriendly. This works because:

• When veganFriendly = 1, only restaurants with vegan = 1 will satisfy 1 >= 1
• When veganFriendly = 0, both vegan = 0 and vegan = 1 will satisfy the condition since both 0 >= 0 and 1 >= 0 are true

For the sorting requirement, we need restaurants ordered by rating (highest first), and ties broken by ID (highest first). Python's sort is stable, so we can sort once using both criteria. The key insight is to use negative values in the sort key (-x[1], -x[0]) to achieve descending order for both rating and ID.

By sorting first before filtering, we ensure that as we iterate through the restaurants and add qualifying ones to our result list, they're already in the correct order. This eliminates the need to sort the filtered results separately, making the solution more efficient and cleaner.

Learn more about Sorting patterns.

Solution Approach

The solution uses a straightforward filtering and sorting approach:

1. Sort the restaurants array: We sort the entire restaurants list using a custom key function lambda x: (-x[1], -x[0]). This sorts by:

   • -x[1]: Negative rating (index 1) for descending order by rating
   • -x[0]: Negative ID (index 0) for descending order by ID when ratings are equal

   This ensures higher-rated restaurants come first, and among restaurants with the same rating, those with higher IDs come first.

2. Initialize result list: Create an empty list ans to store the IDs of qualifying restaurants.

3. Iterate and filter: Loop through each restaurant in the sorted list. For each restaurant, we destructure it into its components:

   for idx, _, vegan, price, dist in restaurants:

   The underscore _ is used for the rating since we don't need it in the filtering logic (we already sorted by it).

4. Apply filter conditions: Check if the restaurant meets all three criteria:

   • vegan >= veganFriendly: Handles both vegan-only filtering (when veganFriendly = 1) and no vegan filtering (when veganFriendly = 0)
   • price <= maxPrice: Ensures the price is within the maximum allowed
   • dist <= maxDistance: Ensures the distance is within the maximum allowed

5. Collect qualifying IDs: If a restaurant passes all filters, append its ID (idx) to the result list.

6. Return the result: Since we sorted before filtering, the IDs in ans are already in the correct order (by rating descending, then by ID descending for ties).

The time complexity is O(n log n) due to sorting, where n is the number of restaurants. The space complexity is O(n) in the worst case when all restaurants pass the filters.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

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

Each restaurant is [id, rating, veganFriendly, price, distance].

Step 1: Sort restaurants by rating (desc), then by id (desc)

Before sorting:

• Restaurant 1: [1,4,1,40,10] - rating=4, id=1
• Restaurant 2: [2,8,0,50,5] - rating=8, id=2
• Restaurant 3: [3,8,1,30,4] - rating=8, id=3
• Restaurant 4: [4,10,0,10,3] - rating=10, id=4
• Restaurant 5: [5,1,1,15,1] - rating=1, id=5

After sorting by (-rating, -id):

1. [4,10,0,10,3] - rating=10 (highest)
2. [3,8,1,30,4] - rating=8, id=3 (higher id than 2)
3. [2,8,0,50,5] - rating=8, id=2
4. [1,4,1,40,10] - rating=4
5. [5,1,1,15,1] - rating=1 (lowest)

Step 2: Apply filters to each restaurant in sorted order

Restaurant 4 [4,10,0,10,3]:

• vegan=0 >= veganFriendly=1? NO (0 >= 1 is false)
• Skip this restaurant

Restaurant 3 [3,8,1,30,4]:

• vegan=1 >= veganFriendly=1? YES (1 >= 1 is true)
• price=30 <= maxPrice=50? YES
• distance=4 <= maxDistance=10? YES
• Add id=3 to result

Restaurant 2 [2,8,0,50,5]:

• vegan=0 >= veganFriendly=1? NO (0 >= 1 is false)
• Skip this restaurant

Restaurant 1 [1,4,1,40,10]:

• vegan=1 >= veganFriendly=1? YES (1 >= 1 is true)
• price=40 <= maxPrice=50? YES
• distance=10 <= maxDistance=10? YES
• Add id=1 to result

Restaurant 5 [5,1,1,15,1]:

• vegan=1 >= veganFriendly=1? YES (1 >= 1 is true)
• price=15 <= maxPrice=50? YES
• distance=1 <= maxDistance=10? YES
• Add id=5 to result

Step 3: Return result Result = [3, 1, 5]

The restaurants are ordered by rating (8, 4, 1) and the IDs maintain this order. Note how the vegan filter condition vegan >= veganFriendly elegantly filtered out non-vegan restaurants (id=4 and id=2) since we required veganFriendly=1.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n log n) where n is the number of restaurants.

• The sorting operation using restaurants.sort() takes O(n log n) time
• The for loop iterates through all restaurants once, which takes O(n) time
• Within the loop, the condition checking and appending operations are O(1)
• Overall time complexity is dominated by the sorting: O(n log n) + O(n) = O(n log n)

Space Complexity: O(n) in the worst case.

• The sort() method in Python uses Timsort algorithm which requires O(n) auxiliary space in the worst case
• The ans list can contain at most n restaurant IDs if all restaurants meet the filtering criteria, requiring O(n) space
• Total space complexity: O(n) + O(n) = O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding the Vegan-Friendly Filter Logic

The Pitfall: Many developers incorrectly implement the vegan-friendly filter as an exact equality check:

# INCORRECT implementation
if veganFriendly == 1 and is_vegan == 1:  # Only checks when filter is on
    filtered_ids.append(restaurant_id)

or

# INCORRECT implementation  
if is_vegan == veganFriendly:  # Excludes non-vegan when filter is off
    filtered_ids.append(restaurant_id)

This misses the key requirement: when veganFriendly = 0, we should include ALL restaurants regardless of their vegan status, not just non-vegan ones.

The Solution: Use the comparison is_vegan >= veganFriendly:

• When veganFriendly = 1: Only restaurants with is_vegan = 1 pass (1 >= 1 is True, 0 >= 1 is False)
• When veganFriendly = 0: All restaurants pass (both 1 >= 0 and 0 >= 0 are True)

2. Sorting In-Place Modifies Original Data

The Pitfall: The current solution sorts the input array in-place with restaurants.sort(), which modifies the original data structure. This could be problematic if:

• The caller expects the original array to remain unchanged
• The same array is used elsewhere in the program
• You need to preserve the original ordering for any reason

The Solution: Create a copy of the array before sorting:

# Create a sorted copy instead of modifying in-place
sorted_restaurants = sorted(restaurants, key=lambda x: (-x[1], -x[0]))

for restaurant_id, rating, is_vegan, price, distance in sorted_restaurants:
    # ... rest of the filtering logic

3. Incorrect Sorting Order

The Pitfall: Forgetting to negate values for descending order or mixing up the indices:

# INCORRECT - sorts in ascending order
restaurants.sort(key=lambda x: (x[1], x[0]))

# INCORRECT - wrong indices (ID is at index 0, rating at index 1)
restaurants.sort(key=lambda x: (-x[0], -x[1]))

The Solution: Always verify:

• Index 0 is the restaurant ID
• Index 1 is the rating
• Use negative values for descending order: (-x[1], -x[0])
• Primary sort key comes first in the tuple (rating), secondary comes second (ID)