Python 1333.py
class Solution:
def filterRestaurants(self, restaurants: List[List[int]], veganFriendly: int, maxPrice: int, maxDistance: int) -> List[int]:
candidates = []
for r in restaurants:
if veganFriendly == 1 and r[2] == 0:
continue
if maxPrice < r[3]:
continue
if maxDistance < r[4]:
continue
candidates.append(( r[1], r[0] ))
return [ c[1] for c in sorted(candidates, reverse = True) ]
Difficulty
and has an acceptance rate of about 64% (50k+ submissions).
Typical patterns to solve this problem:
- Array
- Sorting
AI Disclaimer
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.
See this dedicated page for more details.
Code Walkthrough
Overview
The provided Solution class implements a method that selects restaurant identifiers based on several constraints and orders the result by rating. The algorithm proceeds in three phases: filtering, collection, and sorting. Each phase is expressed with straightforward Python constructs that keep the implementation concise while handling a variety of input conditions.
Filtering Logic
The method begins by iterating over the input list restaurants. For every restaurant record r, three guard clauses decide whether the entry should be excluded:
if veganFriendly == 1 and r[2] == 0:
continue
if maxPrice < r[3]:
continue
if maxDistance < r[4]:
continue
The first clause activates only when the caller requests vegan-friendly results (veganFriendly == 1). In that case any restaurant whose vegan flag (r[2]) is 0 is skipped. When veganFriendly is 0, the condition is bypassed, allowing both vegan and non-vegan establishments to pass.
The second and third clauses enforce upper bounds on price and distance. By comparing the supplied limits (maxPrice, maxDistance) with the restaurant’s price (r[3]) and distance (r[4]), the code discards any entry that exceeds either threshold. These checks are performed before any further processing, ensuring that only viable candidates continue through the pipeline.
Candidate Collection
Restaurants that survive the guard clauses are transformed into a two-element tuple and stored in the list candidates:
candidates.append((r[1], r[0]))
The tuple’s first element is the restaurant’s rating (r[1]), and the second element is its identifier (r[0]). By storing rating first, the subsequent sorting step can order the tuples primarily by rating while preserving the identifier for the final output.
Because the loop appends entries in the order they appear in the original restaurants list, the relative order of restaurants with identical ratings is retained-a consequence of Python’s stable sorting algorithm.
Sorting and Result Extraction
After the loop finishes, the method sorts the candidates list in descending order:
sorted(candidates, reverse=True)
The reverse=True flag flips the default ascending order, so the highest rating appears first. Since each tuple begins with the rating, the sort key is effectively the rating, and the identifier serves as a secondary key when ratings tie. The stable nature of the sort guarantees that ties are resolved by the original input order.
Finally, a list comprehension extracts only the identifiers from the sorted tuples:
return [c[1] for c in sorted(candidates, reverse=True)]
The returned list contains restaurant IDs ordered from highest to lowest rating, respecting the original ordering for equal ratings.
Edge Cases Handled
When the input restaurants list is empty, the loop never executes, leaving candidates empty. The subsequent sort on an empty list yields another empty list, and the final list comprehension returns an empty list-an appropriate response for a lack of data.
If all restaurants fail one of the guard conditions, candidates remains empty for the same reason, and the method again returns an empty list, indicating that no restaurant satisfies the constraints.
When multiple restaurants share the same rating, the stable sort preserves their input sequence. This behavior ensures deterministic output without requiring additional tie-breaking logic.
If veganFriendly is set to 0, the vegan filter is effectively disabled, allowing the method to consider both vegan and non-vegan establishments. Conversely, when veganFriendly is 1, any restaurant with a vegan flag of 0 is excluded, demonstrating correct handling of the optional filter.
Performance Optimizations
The implementation avoids unnecessary work by short-circuiting the evaluation of each restaurant. The continue statements exit the loop early for any record that violates a constraint, preventing the creation of a tuple for ineligible entries. This early exit reduces both CPU cycles and memory allocations.
Collecting only the rating and identifier in the candidates list minimizes the amount of data that must be sorted. By discarding the other fields (price, distance, vegan flag) after filtering, the sort operates on a compact structure, which speeds up the comparison operations.
Sorting is performed only on the filtered subset rather than the entire input list. In scenarios where many restaurants are filtered out, this dramatically reduces the number of elements the sort algorithm must handle, leading to faster overall execution.
The final list comprehension extracts identifiers in a single pass over the already sorted list, avoiding any additional loops or intermediate structures. This streamlined extraction contributes to the method’s efficiency.
ELI5 - Simplified Explanation
Imagine you have a big list of restaurants, and each one is described by a few numbers, kind of like secret codes on a badge. Some codes tell us if the food is vegan, how much it costs, and how far away it is.
The computer starts with an empty notebook called candidates to keep track of the places that fit your rules. It looks at every restaurant one by one. First, it checks if you want a vegan meal. If the restaurant does not have vegan options but you asked for them, the computer skips that place entirely and moves to the next one. Next, it checks if the price is too high or if the restaurant is too far away. If the price is higher than your limit or the distance is too long, it skips those as well.
If a restaurant passes all those checks, it is a winner. The computer writes down the rating and the ID number of that restaurant in the notebook. Once every single restaurant has been looked at, the computer sorts the list of winners by their ratings so the best ones are at the top. Finally, it pulls out only the ID numbers of those winners so you can see which restaurants are perfect for you.
Code Quality
Complexity Analysis
As a rule of thumb, the maximum input size for one second execution time is
- factorial: up to 10 elements
- exponential: up to 20 elements
- polynomial: a few thousand elements
- loglinear: up to 100,000 elements
- linear: a few million elements
- logarithmic: a billion elements
- constant: practically unlimited
Other Solutions
Obviously, I did that after I solved the problem myself.
In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.
And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.
(click on a column header to sort the table)
| author | ||||||||
|---|---|---|---|---|---|---|---|---|
| author | solutions | |||||||
| www | AlgoMonster | C++ | Java | Python | TS | |||
| WalkCCC | C++ | Java | Python | |||||
| leetcode.ca | C++ | Java | Python | Go | TS | |||
| Progiez | C++ | Java | Python | |||||
| github | black-shadows | C++ | ||||||
| charles-wangkai | Java | |||||||
| fsq | C++ | |||||||
| haoel | C++ | |||||||
| JoshCrozier | JS | |||||||
| lkwq007 | Python | |||||||
| lzl124631x | C++ | |||||||
| suxrobGM | C# | |||||||
| varunu28 | Java | |||||||
| AlgoMonster | C++, Python, Java, TypeScript | |||||||
| WalkCCC | C++, Python, Java | |||||||
| leetcode.ca | C++, Go, Java, Python, TypeScript | |||||||
| Progiez | C++, Java, Python | |||||||
| black-shadows | C++, C++ | |||||||
| charles-wangkai | Java | |||||||
| fsq | C++ | |||||||
| haoel | C++ | |||||||
| JoshCrozier | JavaScript | |||||||
| lkwq007 | Python | |||||||
| lzl124631x | C++ | |||||||
| suxrobGM | C# | |||||||
| varunu28 | Java |
Videos
Solved On The Same Day
- problem 1227: Airplane Seat Assignment Probability
- problem 1315: Sum of Nodes with Even-Valued Grandparent
- problem 1325: Delete Leaves With a Given Value
- problem 1344: Angle Between Hands of a Clock
- problem 1220: Count Vowels Permutation
Extra
- Tech Stack - my development environment and tools
- AI - how AI helped me create this website (NOT solving the problems)
- Progress - progression over time
- Quality - code quality