Code Implementation

class Solution:
    def filterRestaurants(self, restaurants, veganFriendly, maxPrice, maxDistance):
        filtered = []
        for rest in restaurants:
            id, rating, vegan, price, distance = rest
            if veganFriendly and not vegan:
                continue
            if price > maxPrice or distance > maxDistance:
                continue
            filtered.append((rating, id))
        # Sort by rating descending, then id descending
        filtered.sort(reverse=True)
        return [id for rating, id in filtered]
      

class Solution {
public:
    vector<int> filterRestaurants(vector<vector<int>>& restaurants, int veganFriendly, int maxPrice, int maxDistance) {
        vector<pair<int, int>> filtered;
        for (auto& rest : restaurants) {
            int id = rest[0], rating = rest[1], vegan = rest[2], price = rest[3], distance = rest[4];
            if (veganFriendly == 1 && vegan == 0) continue;
            if (price > maxPrice || distance > maxDistance) continue;
            filtered.push_back({rating, id});
        }
        sort(filtered.rbegin(), filtered.rend());
        vector<int> result;
        for (auto& p : filtered) result.push_back(p.second);
        return result;
    }
};
      

class Solution {
    public List<Integer> filterRestaurants(int[][] restaurants, int veganFriendly, int maxPrice, int maxDistance) {
        List<int[]> filtered = new ArrayList<>();
        for (int[] rest : restaurants) {
            int id = rest[0], rating = rest[1], vegan = rest[2], price = rest[3], distance = rest[4];
            if (veganFriendly == 1 && vegan == 0) continue;
            if (price > maxPrice || distance > maxDistance) continue;
            filtered.add(new int[]{rating, id});
        }
        filtered.sort((a, b) -> b[0] != a[0] ? b[0] - a[0] : b[1] - a[1]);
        List<Integer> res = new ArrayList<>();
        for (int[] f : filtered) res.add(f[1]);
        return res;
    }
}
      

var filterRestaurants = function(restaurants, veganFriendly, maxPrice, maxDistance) {
    let filtered = [];
    for (const [id, rating, vegan, price, distance] of restaurants) {
        if (veganFriendly && !vegan) continue;
        if (price > maxPrice || distance > maxDistance) continue;
        filtered.push([rating, id]);
    }
    filtered.sort((a, b) => b[0] - a[0] || b[1] - a[1]);
    return filtered.map(x => x[1]);
};
      

Problem Description

You are given a list of restaurants, where each restaurant is represented as a list of five integers: [id, rating, veganFriendly, price, distance]. You are also given three parameters: veganFriendly (either 0 or 1), maxPrice, and maxDistance.

Your task is to filter the list of restaurants using the following criteria:

• If veganFriendly == 1, only include restaurants where veganFriendly == 1 in their data.
• Only include restaurants where price <= maxPrice.
• Only include restaurants where distance <= maxDistance.

Return a list of restaurant ids in the sorted order. Each restaurant can only appear once, and all input values are integers.

Thought Process

The problem is essentially about filtering and sorting a list of restaurants based on several criteria. The filtering is straightforward: check each restaurant to see if it meets the requirements for vegan-friendliness, price, and distance.

Once the filtering is done, we need to sort the list by two keys: rating (descending) and id (descending). This means that restaurants with higher ratings come first, and if two restaurants have the same rating, the one with the higher id comes first.

The brute-force approach is to check each restaurant one by one, add those that pass the filters to a new list, and then sort this list as required. There is no need for further optimization, as all steps are linear or use efficient built-in sorting.

The main conceptual shift is recognizing that the problem is about applying filters and then sorting, rather than, say, searching or dynamic programming.

Solution Approach

Let's break down the solution step by step:

1. Initialize a new list for filtered restaurants.
   • We will store tuples or arrays of (rating, id) for restaurants that pass all filters.
2. Iterate over each restaurant:
   • If veganFriendly == 1 and the restaurant is not vegan-friendly, skip it.
   • If price > maxPrice, skip it.
   • If distance > maxDistance, skip it.
   • If all conditions are satisfied, add (rating, id) to the filtered list.
3. Sort the filtered list:
   • First by rating in descending order.
   • If ratings are equal, by id in descending order.
   • Sorting can be done with a custom comparator or key function.
4. Extract the ids from the sorted list and return them.
   • Return only the ids, as required by the problem statement.

This approach is simple and effective because the constraints are small enough that a single pass plus a sort is efficient.

Example Walkthrough

Suppose we have the following 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

Step-by-step:

1. Check each restaurant:
   • Restaurant 1: vegan-friendly, price 40 ≤ 50, distance 10 ≤ 10 ⇒ pass
   • Restaurant 2: not vegan-friendly, veganFriendly filter is on ⇒ skip
   • Restaurant 3: vegan-friendly, price 30 ≤ 50, distance 4 ≤ 10 ⇒ pass
   • Restaurant 4: not vegan-friendly, veganFriendly filter is on ⇒ skip
   • Restaurant 5: vegan-friendly, price 15 ≤ 50, distance 1 ≤ 10 ⇒ pass
2. Filtered list: [(4,1), (8,3), (1,5)] — but actually, capture ratings and ids: [(4,1), (8,3), (1,5)]
3. Sort by rating descending, then id descending:
   • (8,3), (4,1), (1,5)
4. Return ids: [3,1,5]

Time and Space Complexity

Brute-force approach:

• Filtering: O(n), where n is the number of restaurants.
• Sorting: O(n log n), as we sort the filtered list (at most n elements).
• Total: O(n log n), since sorting dominates.
• Space: O(n), for the filtered list and output.

• This is already the optimal approach for this problem, as sorting is necessary for the required output order.

Summary

The solution involves filtering restaurants based on vegan-friendliness, price, and distance, and then sorting the results by rating and id in descending order. The approach is direct and efficient, leveraging simple iteration and sorting. The problem illustrates how clear requirements and constraints allow for a straightforward, readable solution without the need for advanced data structures or algorithms.