Problem 1333

Abstract / Summary

Filter a list of restaurants by vegan friendliness, maximum price, and maximum distance from a point.

Note

The full problem description, including helpful examples, can be found on LeetCode.

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) ]
14 lines | 520 bytes | submitted October 29, 2023 | GitHub   tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 64% (50k+ submissions).

Typical patterns to solve this problem:
  • Array
  • Sorting
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
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.
LeetCode profile | GitHub repo

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.

written by openai gpt

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.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 7 | μ = 7.07 | σ = 0.86

Complexity Analysis

Time: loglinear
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
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
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
24 links | 13 authors | 7 languages

Videos

2 videos   did my crawler come up with invalid videos ? drop me a line.

Solved On The Same Day

6 solutions   October 29, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • 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