Filter Restaurants by Vegan-Friendly, Price and Distance

You are given a list of restaurants, where each restaurant is represented as [id, rating, veganFriendly, price, distance]. Given three filters, veganFriendly, maxPrice, and maxDistance, return the list of restaurant ids after filtering. The result should be sorted by rating from highest to lowest. If two restaurants have the same rating, sort them by id from highest to lowest.

This is LeetCode 1333: Filter Restaurants by Vegan-Friendly, Price and Distance.

Why this problem matters

Filtering data and then sorting it by multiple keys is one of the most common patterns in real-world programming. You do it when building search results, ranking products, or surfacing recommendations. This problem distills that workflow into a clean exercise: apply a set of constraints to remove items, then sort the survivors by a composite key.

The twist that makes this problem interesting is the conditional filter. When veganFriendly is 1, you only keep restaurants where veganFriendly is also 1. When the filter is 0, you keep all restaurants regardless of their vegan status. This conditional logic is easy to get wrong if you do not think about it carefully.

Once you solve this, you will recognize the same filter-then-sort pattern in problems like "Largest Values From Labels" and "Relative Sort Array." The building blocks are reusable.

The key insight

This problem separates into two independent steps: filter, then sort. The filtering step checks three conditions. Price must be at most maxPrice. Distance must be at most maxDistance. The vegan check is conditional: you only enforce it when the veganFriendly parameter is 1. When it is 0, every restaurant passes the vegan check regardless of its own vegan status.

After filtering, the sort uses two keys. The primary key is rating in descending order. The tiebreaker is id in descending order. In Python, you can handle both keys in a single sort call by negating the values.

The solution

def filter_restaurants(restaurants, vegan_friendly, max_price, max_distance):
    filtered = []
    for r in restaurants:
        rid, rating, vegan, price, distance = r
        if vegan_friendly and not vegan:
            continue
        if price > max_price or distance > max_distance:
            continue
        filtered.append(r)

    filtered.sort(key=lambda r: (-r[1], -r[0]))

    return [r[0] for r in filtered]

The solution loops through every restaurant and applies three checks. First, if the veganFriendly filter is active (value 1) and the restaurant is not vegan-friendly, skip it. Second, if the restaurant's price exceeds maxPrice or its distance exceeds maxDistance, skip it. Everything that survives both checks gets added to the filtered list.

The sort step uses a tuple key (-r[1], -r[0]). Negating the rating and the id means Python's default ascending sort produces descending order for both keys. Rating is the primary sort key, and id is the tiebreaker.

Finally, a list comprehension extracts just the ids from the sorted list.

Visual walkthrough

The walkthrough shows the full pipeline. First you scan every restaurant against the filter criteria. Then you keep only the ones that pass. Then you sort by rating descending (with id as a tiebreaker). Finally you extract the ids to produce the answer.

Complexity analysis

Time is O(n log n) where n is the number of restaurants. The filtering step is O(n) since you scan every restaurant once. The sort step is O(k log k) where k is the number of restaurants that pass the filter. In the worst case, all restaurants pass and k = n, so the overall time is O(n log n).

Space is O(n) for the filtered list. In the worst case, every restaurant passes the filter and you store all n of them.

The building blocks

1. Conditional filtering

The pattern of iterating through a collection and keeping only items that satisfy a set of predicates:

filtered = []
for item in items:
    if not passes_all_filters(item):
        continue
    filtered.append(item)

The key detail here is the conditional filter. The vegan check only applies when the filter parameter is 1. You can express this as if vegan_friendly and not vegan: continue. When vegan_friendly is 0, the condition short-circuits and every restaurant passes. This pattern of "only apply a filter when a flag is set" appears in many search and query problems.

2. Multi-key sorting with negation

The pattern of sorting by multiple criteria using a tuple key:

items.sort(key=lambda x: (-x.primary, -x.secondary))

Negating numeric values inside the tuple lets you sort descending on each key using Python's default ascending sort. This avoids the complexity of functools.cmp_to_key and works as long as your keys are numeric. You will see this pattern in ranking problems, leaderboard problems, and any scenario where you need to break ties across multiple dimensions.

Edge cases

• veganFriendly is 0: every restaurant passes the vegan check. You still need to filter by price and distance.
• All restaurants are filtered out: return an empty list. No items survive the filter step.
• All restaurants have the same rating: the tiebreaker is id descending, so the restaurant with the largest id comes first.
• Single restaurant: if it passes the filters, return its id in a list. If not, return an empty list.
• Price or distance exactly equals the max: the problem uses <=, so the restaurant should pass. Make sure your comparison is not strictly less than.

From understanding to recall

You have seen how filter-then-sort works: scan for items that meet the criteria, sort by a composite key, and extract the ids. The logic is clean and the code is short. But under interview pressure, the details matter. Do you apply the vegan filter when the parameter is 0 or 1? Do you sort ascending or descending? Do you break ties by id or by rating?

Spaced repetition closes these gaps. You practice writing the conditional filter, the negated tuple sort key, and the id extraction from memory at increasing intervals. After a few rounds, the pattern is automatic. You see "filter by criteria and sort by multiple keys" in a problem description, and the code flows out without hesitation.

Related posts

• Sort an Array - Sorting fundamentals
• Relative Sort Array - Custom ordering
• Largest Values From Labels - Filtering with constraints

CodeBricks breaks Filter Restaurants into its conditional filtering and multi-key sorting building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a filter-and-sort problem shows up in your interview, you do not think about it. You just write it.