# Filter Restaurants by Vegan-Friendly, Price and Distance
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/filter-restaurants-by-vegan-friendly-price-and-distance)
Canonical: https://scaleengineer.com/dsa/problems/filter-restaurants-by-vegan-friendly-price-and-distance
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Yelp](https://scaleengineer.com/companies/yelp)
---
## Problem
Given the array `restaurants` where `restaurants[i] = [idi, ratingi, veganFriendlyi, pricei, distancei]`. You have to filter the restaurants using three filters.

The `veganFriendly` filter will be either _true_ (meaning you should only include restaurants with `veganFriendlyi` set to true) or _false_ (meaning you can include any restaurant). In addition, you have the filters `maxPrice` and `maxDistance` which are the maximum value for price and distance of restaurants you should consider respectively.

Return the array of restaurant _**IDs**_ after filtering, ordered by **rating** from highest to lowest. For restaurants with the same rating, order them by _**id**_ from highest to lowest. For simplicity `veganFriendlyi` and `veganFriendly` take value _1_ when it is _true_, and _0_ when it is _false_.

**Example 1:**

**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
**Output:** [3,1,5] 
**Explanation:** 
The restaurants are:
Restaurant 1 [id=1, rating=4, veganFriendly=1, price=40, distance=10]
Restaurant 2 [id=2, rating=8, veganFriendly=0, price=50, distance=5]
Restaurant 3 [id=3, rating=8, veganFriendly=1, price=30, distance=4]
Restaurant 4 [id=4, rating=10, veganFriendly=0, price=10, distance=3]
Restaurant 5 [id=5, rating=1, veganFriendly=1, price=15, distance=1] 
After filter restaurants with veganFriendly = 1, maxPrice = 50 and maxDistance = 10 we have restaurant 3, restaurant 1 and restaurant 5 (ordered by rating from highest to lowest). 

**Example 2:**

**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 = 0, maxPrice = 50, maxDistance = 10
**Output:** [4,3,2,1,5]
**Explanation:** The restaurants are the same as in example 1, but in this case the filter veganFriendly = 0, therefore all restaurants are considered.

**Example 3:**

**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 = 0, maxPrice = 30, maxDistance = 3
**Output:** [4,5]

**Constraints:**

* `1 <= restaurants.length <= 10^4`
* `restaurants[i].length == 5`
* `1 <= idi, ratingi, pricei, distancei <= 10^5`
* `1 <= maxPrice, maxDistance <= 10^5`
* `veganFriendlyi` and `veganFriendly` are 0 or 1.
* All `idi` are distinct.

# Approaches
## Sort then Filter
This straightforward but less efficient approach involves sorting the entire list of restaurants first, based on the required criteria (rating and ID). After sorting, it iterates through the now-ordered list and filters out restaurants that do not meet the given conditions (`veganFriendly`, `maxPrice`, `maxDistance`).
**Time:** O(N log N), where N is the number of restaurants. Sorting the entire array is the dominant operation. · **Space:** O(N) in the worst case. This is for the space required by the sorting algorithm (e.g., TimSort's worst-case space) and the result list, where N is the total number of restaurants.
**Pros:** Conceptually simple to understand: sort everything, then pick what you need.
**Cons:** Inefficient as it performs a costly sort operation on all N restaurants, including those that will be filtered out. This is particularly wasteful if the filters are very restrictive.
### Explanation
The main idea is to establish the final desired order for all restaurants before checking if they are valid candidates. A custom `Comparator` is used to sort the `restaurants` array. The comparator prioritizes higher ratings, and for ties in rating, it prioritizes higher IDs. Once the entire array is sorted, a single pass is performed to check each restaurant against the three filters. Restaurants that pass all filters are added to a result list. Since the main array was already sorted, the restaurants are added to the result list in the correct final order, preserving the sort.

```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<Integer> filterRestaurants(int[][] restaurants, int veganFriendly, int maxPrice, int maxDistance) {
        // 1. Sort the entire array first
        Arrays.sort(restaurants, (a, b) -> {
            if (a[1] != b[1]) {
                return Integer.compare(b[1], a[1]); // Sort by rating descending
            } else {
                return Integer.compare(b[0], a[0]); // Sort by ID descending
            }
        });

        List<Integer> result = new ArrayList<>();
        
        // 2. Iterate and filter
        for (int[] r : restaurants) {
            // The veganFriendly filter applies only if veganFriendly is 1.
            if (veganFriendly == 1 && r[2] == 0) {
                continue;
            }
            if (r[3] <= maxPrice && r[4] <= maxDistance) {
                result.add(r[0]);
            }
        }
        
        return result;
    }
}
```
### Algorithm
- Define a custom `Comparator` to sort restaurants by rating (descending) and then ID (descending).
- Sort the entire `restaurants` array using this comparator.
- Initialize an empty list, `result`, to store the final restaurant IDs.
- Iterate through each `restaurant` in the sorted `restaurants` array.
- For each restaurant, check if it satisfies the `veganFriendly`, `maxPrice`, and `maxDistance` constraints.
- If all conditions are met, add the restaurant's ID (`restaurant[0]`) to the `result` list.
- Return the `result` list.

## Filter then Sort using a Temporary List
A more efficient approach is to first filter the restaurants and then sort only the ones that meet the criteria. This avoids the overhead of sorting elements that will be discarded.
**Time:** O(N + K log K), where N is the total number of restaurants and K is the number of restaurants that pass the filters. O(N) for filtering and O(K log K) for sorting. This is significantly better than O(N log N) when K is small. · **Space:** O(K) to store the filtered list of restaurants, where K is the number of filtered restaurants. In the worst case, K=N, and the complexity becomes O(N).
**Pros:** More efficient than the 'Sort then Filter' approach, especially when filters are strict.; Avoids unnecessary sorting operations on irrelevant data.
**Cons:** Requires extra space (O(K)) to store the filtered list before sorting.
### Explanation
This method involves two main passes. In the first pass, we iterate through the original `restaurants` array. Each restaurant is checked against the `veganFriendly`, `maxPrice`, and `maxDistance` filters. If a restaurant passes all checks, it is added to a temporary list. After this filtering pass, the temporary list contains only the valid restaurants. In the second step, we sort this (potentially much smaller) temporary list using the same custom comparator as before (rating descending, then ID descending). Finally, we create the result list by extracting the IDs from the sorted temporary list.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public List<Integer> filterRestaurants(int[][] restaurants, int veganFriendly, int maxPrice, int maxDistance) {
        List<int[]> filtered = new ArrayList<>();
        
        // 1. Filter the restaurants
        for (int[] r : restaurants) {
            if (veganFriendly == 1 && r[2] == 0) {
                continue;
            }
            if (r[3] <= maxPrice && r[4] <= maxDistance) {
                filtered.add(r);
            }
        }
        
        // 2. Sort the filtered list
        Collections.sort(filtered, (a, b) -> {
            if (a[1] != b[1]) {
                return Integer.compare(b[1], a[1]); // Sort by rating descending
            } else {
                return Integer.compare(b[0], a[0]); // Sort by ID descending
            }
        });
        
        // 3. Extract IDs
        List<Integer> result = new ArrayList<>();
        for (int[] r : filtered) {
            result.add(r[0]);
        }
        
        return result;
    }
}
```
### Algorithm
- Initialize an empty list, `filteredRestaurants`.
- Iterate through the input `restaurants` array.
- For each restaurant, if it satisfies the `veganFriendly`, `maxPrice`, and `maxDistance` filters, add it to `filteredRestaurants`.
- Sort the `filteredRestaurants` list using a custom `Comparator` (rating descending, then ID descending).
- Initialize an empty list, `resultIds`.
- Iterate through the sorted `filteredRestaurants` and add each restaurant's ID to `resultIds`.
- Return `resultIds`.

## Filter and Sort using Java Streams
This approach uses the modern Java Stream API to achieve the same 'Filter then Sort' logic in a more concise and declarative way. It chains filtering and sorting operations into a single, readable pipeline.
**Time:** O(N + K log K), where N is the total number of restaurants and K is the number of filtered restaurants. The performance is identical to the manual 'Filter then Sort' approach. · **Space:** O(K) to store the filtered elements for sorting and the final result, where K is the number of filtered restaurants. In the worst case, this is O(N).
**Pros:** Highly readable and concise, expressing intent clearly.; Functionally equivalent to the optimal manual approach.; Leverages modern Java features for cleaner code.
**Cons:** May have a slight performance overhead compared to manual loops due to stream object creation, though this is usually negligible.; Can be less intuitive for developers not yet comfortable with functional programming and streams.
### Explanation
This is the most idiomatic way to solve the problem in modern Java. We create a stream from the `restaurants` array. The `filter()` operation is used to apply the `veganFriendly`, `maxPrice`, and `maxDistance` conditions. Because streams are lazy, these filters are applied efficiently. The `sorted()` operation is then called on the resulting stream of filtered restaurants, using a comparator to sort by rating (desc) and then ID (desc). The `map()` operation transforms the stream of sorted restaurant arrays into a stream of their IDs. Finally, the `collect()` terminal operation gathers the IDs into a list.

```java
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

class Solution {
    public List<Integer> filterRestaurants(int[][] restaurants, int veganFriendly, int maxPrice, int maxDistance) {
        return Arrays.stream(restaurants)
            .filter(r -> (veganFriendly == 0 || r[2] == 1) && r[3] <= maxPrice && r[4] <= maxDistance)
            .sorted((a, b) -> {
                if (a[1] != b[1]) {
                    return Integer.compare(b[1], a[1]);
                } else {
                    return Integer.compare(b[0], a[0]);
                }
            })
            .map(r -> r[0])
            .collect(Collectors.toList());
    }
}
```
### Algorithm
- Create a stream from the `restaurants` array.
- Chain a `filter()` operation to the stream to select restaurants based on the three criteria.
- Chain a `sorted()` operation with a custom `Comparator` to sort the filtered stream by rating (desc) and then ID (desc).
- Chain a `map()` operation to extract the ID from each restaurant object.
- Use `collect(Collectors.toList())` to terminate the stream and gather the results into a list.
- Return the resulting list.

# Solutions
### Java

```java
class Solution {
public
  List<Integer> filterRestaurants(int[][] restaurants, int veganFriendly,
                                  int maxPrice, int maxDistance) {
    Arrays.sort(restaurants, (a, b)->a[1] == b[1] ? b[0] - a[0] : b[1] - a[1]);
    List<Integer> ans = new ArrayList<>();
    for (int[] r : restaurants) {
      if (r[2] >= veganFriendly && r[3] <= maxPrice && r[4] <= maxDistance) {
        ans.add(r[0]);
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> filterRestaurants(vector<vector<int>> &restaurants,
                                int veganFriendly, int maxPrice,
                                int maxDistance) {
    sort(restaurants.begin(), restaurants.end(),
         [](const vector<int> &a, const vector<int> &b) {
           if (a[1] != b[1]) {
             return a[1] > b[1];
           }
           return a[0] > b[0];
         });
    vector<int> ans;
    for (auto &r : restaurants) {
      if (r[2] >= veganFriendly && r[3] <= maxPrice && r[4] <= maxDistance) {
        ans.push_back(r[0]);
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def filterRestaurants(self, restaurants: List[List[int]], veganFriendly: int, maxPrice: int, maxDistance: int, ) -> List[int]: restaurants . sort(key=lambda x: (- x[1], - x[0])) ans = [] for idx, _, vegan, price, dist in restaurants: if vegan >= veganFriendly and price <= maxPrice and dist <= maxDistance: ans . append(idx) return ans

```