LeetCode 1333 - Filter Restaurants by Vegan-Friendly, Price and Distance

The problem is asking us to filter and sort a list of restaurants based on multiple criteria. Each restaurant is represe

leetcodemediumarraysorting

LeetCode Problem 1333

Difficulty: 🟡 Medium
Topics: Array, Sorting

Solution

Problem Understanding

The problem is asking us to filter and sort a list of restaurants based on multiple criteria. Each restaurant is represented as an array [id, rating, veganFriendly, price, distance]. We are given three filters: veganFriendly, maxPrice, and maxDistance. The veganFriendly filter is either 1 or 0, where 1 means we only include restaurants that are vegan-friendly and 0 means we ignore this filter. The maxPrice and maxDistance filters define the maximum price and distance a restaurant can have to be considered.

After filtering the restaurants according to these conditions, we need to return a list of restaurant IDs sorted primarily by rating from highest to lowest. If two restaurants have the same rating, we break the tie by ID, from highest to lowest.

Constraints indicate that the number of restaurants can be up to 10^4, which is moderate. Each attribute is bounded by 10^5, and all restaurant IDs are distinct, so we do not need to handle duplicates. Key edge cases include situations where all restaurants are filtered out, all restaurants have the same rating, or only a subset passes the vegan-friendly filter.

Approaches

The brute-force approach is straightforward: iterate through all restaurants and check each filter condition. If a restaurant passes, we keep it. After filtering, we sort the restaurants based on rating and ID. This works because the number of restaurants (10^4) is manageable for sorting.

The optimal approach uses the same idea but combines filtering and sorting efficiently. Since sorting with a custom key in Python or Go is efficient (O(n log n)), there is no faster asymptotic approach here. The key insight is to use a sorting key that naturally implements both primary and secondary sorting criteria (rating and ID) in descending order.

Approach Time Complexity Space Complexity Notes
Brute Force O(n log n) O(n) Filter and sort using built-in functions
Optimal O(n log n) O(n) Same as brute force but with combined sorting key for efficiency

Algorithm Walkthrough

  1. Initialize an empty list to store restaurants that pass the filters.
  2. Iterate through each restaurant in the input array:
  • If veganFriendly filter is 1, skip any restaurant where veganFriendly is 0.
  • Skip any restaurant where price exceeds maxPrice.
  • Skip any restaurant where distance exceeds maxDistance.
  • If the restaurant passes all filters, add it to the filtered list.
  1. Sort the filtered list in descending order by rating. For restaurants with the same rating, sort by id in descending order. In Python, this can be achieved using a custom sorting key (rating, id) with reverse=True.
  2. Extract the id from each restaurant in the sorted list and return the list of IDs.

Why it works: Filtering ensures only valid restaurants are considered. Sorting by a combined key guarantees that the primary and secondary ordering conditions are respected, which produces the correct result as specified.

Python Solution

from typing import List

class Solution:
    def filterRestaurants(self, restaurants: List[List[int]], veganFriendly: int, maxPrice: int, maxDistance: int) -> List[int]:
        filtered = []
        for r in restaurants:
            id, rating, vegan, price, distance = r
            if veganFriendly and vegan == 0:
                continue
            if price > maxPrice or distance > maxDistance:
                continue
            filtered.append(r)
        
        # Sort by rating descending, then by id descending
        filtered.sort(key=lambda x: (x[1], x[0]), reverse=True)
        
        return [r[0] for r in filtered]

In this Python solution, the code iterates through all restaurants to check filters and constructs a new list filtered of only valid restaurants. The sort function uses a lambda key to sort first by rating and then by id, both in descending order. Finally, a list comprehension extracts just the IDs.

Go Solution

import "sort"

func filterRestaurants(restaurants [][]int, veganFriendly int, maxPrice int, maxDistance int) []int {
    filtered := [][]int{}
    
    for _, r := range restaurants {
        id, rating, vegan, price, distance := r[0], r[1], r[2], r[3], r[4]
        if veganFriendly == 1 && vegan == 0 {
            continue
        }
        if price > maxPrice || distance > maxDistance {
            continue
        }
        filtered = append(filtered, r)
    }
    
    sort.Slice(filtered, func(i, j int) bool {
        if filtered[i][1] != filtered[j][1] {
            return filtered[i][1] > filtered[j][1]
        }
        return filtered[i][0] > filtered[j][0]
    })
    
    result := make([]int, len(filtered))
    for i, r := range filtered {
        result[i] = r[0]
    }
    
    return result
}

In Go, sort.Slice is used with a custom comparator to implement descending sort for both rating and ID. The filtered restaurants are appended to a slice, and IDs are extracted into the result slice.

Worked Examples

Example 1

Input: [[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

  1. Filtering:
  • Restaurant 1: vegan=1, price=40, distance=10 → keep
  • Restaurant 2: vegan=0 → discard
  • Restaurant 3: vegan=1, price=30, distance=4 → keep
  • Restaurant 4: vegan=0 → discard
  • Restaurant 5: vegan=1, price=15, distance=1 → keep
  1. Sorted by rating descending, ID descending: [3 (8), 1 (4), 5 (1)]
  2. Output: [3,1,5]

Example 2

Input: veganFriendly=0, maxPrice=50, maxDistance=10

All restaurants pass price and distance filters. Sorting by rating then ID gives [4,3,2,1,5].

Example 3

Input: veganFriendly=0, maxPrice=30, maxDistance=3

Only restaurant 4 (price 10, distance 3) and restaurant 5 (price 15, distance 1) pass filters. Sorting yields [4,5].

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Filtering is O(n), sorting is O(n log n)
Space O(n) Space for filtered list and result list

Filtering is linear in the number of restaurants. Sorting dominates time complexity at O(n log n). Additional space is required to store the filtered restaurants.

Test Cases

# Provided examples
assert Solution().filterRestaurants([[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]], 1, 50, 10) == [3,1,5]
assert Solution().filterRestaurants([[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]], 0, 50, 10) == [4,3,2,1,5]
assert Solution().filterRestaurants([[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]], 0, 30, 3) == [4,5]

# Edge cases
assert Solution().filterRestaurants([], 0, 100, 100) == []  # empty input
assert Solution().filterRestaurants([[1,5,1,10,1]], 1, 10, 1) == [1]  # single restaurant passes
assert Solution().filterRestaurants([[1,5,1,10,1]], 0, 5, 1) == []  # single restaurant filtered out by price
assert Solution().filterRestaurants([[1,5,0,10,1],[2,5,0,10,1]], 0, 10, 1) == [2,1]  # same rating, different IDs
Test Why
Empty input Validates function handles zero restaurants
Single restaurant passes Ensures filter works correctly
Single restaurant filtered Ensures filter removes restaurants outside limits
Same rating, multiple IDs Checks secondary sorting by ID

Edge Cases

The first edge case is an empty restaurant list. The solution correctly returns an empty list since there is nothing to filter or sort.

The second edge case occurs when all restaurants have the same rating but different IDs. The algorithm must correctly sort by ID descending in this case, and