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

MediumArraySorting
Leetcode Link

Problem Description

In this problem, you are given an array restaurants, where each element in the array represents a restaurant and is itself an array of the form [id_i, rating_i, veganFriendly_i, price_i, distance_i]. You are required to filter these restaurants based on three criteria: whether they are vegan-friendly, their price, and their distance from the user.

The veganFriendly filter is a boolean that, when true, means you should only include restaurants where veganFriendly_i is set to 1. When veganFriendly is false, you can include any restaurant, regardless of its veganFriendly_i value.

Additionally, you are given a maximum price maxPrice and a maximum distance maxDistance. Restaurants exceeding either of these values should not be included in the final list.

Your task is to return an array of restaurant IDs that satisfy all three filter conditions. The IDs should be ordered first by the restaurant's rating in descending order, and in the case of a tie in ratings, by the restaurant's ID in descending order.

Intuition

To solve this problem, we first need to deal with the restaurant ordering. Given that we want the restaurants sorted by rating and ID as secondary criteria, we can achieve this by sorting the restaurants array. In Python, we can use the sort() method with a custom key function that sorts by rating in descending order first and then by ID in descending order as a tiebreaker.

Once we have the sorted array, we need to filter out the restaurants according to the given criteria. We accomplish this by iterating over each restaurant and checking if it satisfies the conditions of being vegan-friendly (if required), within the maximum price, and within the maximum distance. If a restaurant meets all the conditions, we add its ID to our final list of restaurant IDs.

The reason behind sorting the array first before filtering is to ensure that once the filtering is done, we don't need to sort the resulting list again, as it will already be ordered according to the required criteria.

The key aspects of this solution are understanding how to sort the array according to multiple criteria and filtering the elements of the array based on given thresholds.

Learn more about Sorting patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Solution Approach

The solution approach can be detailed through the following steps, which encompass the use of sorting and filtering in Python:

  1. Sorting: Firstly, the given list of restaurants is sorted in a descending order based on the rating_i, and in the case where two restaurants have the same rating_i, they're further sorted by id_i in descending order. This is done using the sort() method with a lambda function as the key parameter. The lambda function returns a tuple (-x[1], -x[0]). Here, x represents an element (which is a list) in restaurants. The minus sign (-) is used to sort in descending order since Python's sort functions sort in ascending order by default. The tuple essentially says "sort by the second element (rating) in descending order, and if those are equal, sort by the first element (ID) in descending order".

    1restaurants.sort(key=lambda x: (-x[1], -x[0]))

  2. Filtering: After sorting, the next step is to filter the restaurants based on the criteria:

    • If veganFriendly is 1, then only include restaurants where veganFriendly_i is also 1.
    • Include restaurants where the price_i is less than or equal to the maxPrice.
    • Include restaurants where the distance_i is less than or equal to the maxDistance.

    We use a for loop to iterate through each restaurant in the sorted restaurants list. For each restaurant (represented as a sublist), we check the three conditions mentioned above.

    1for idx, _, vegan, price, dist in restaurants:
2    if vegan >= veganFriendly and price <= maxPrice and dist <= maxDistance:
3        ans.append(idx)

    We declare an empty list ans to store the IDs of the restaurants that meet all of the filters. For each restaurant, idx represents its ID. We only append idx to ans if all the conditions are met.

  3. Return the Result: Once the iteration is complete, the ans list contains the IDs of the restaurants that have passed through the filters, sorted as required. This list is then returned as the final answer.

    1return ans

The algorithms used in this implementation include sorting and simple linear iteration for filtering. The data structure used is a list. No complex patterns or data structures like trees, graphs, or dynamic programming are used; the solution is straightforward and only involves array manipulation.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following is the prefix sum of array [1, 2, 3, 4, 5]?

Example Walkthrough

Let's walkthrough an example to illustrate the solution approach.

Suppose we have the following list of restaurants and the filters veganFriendly, maxPrice, and maxDistance given as:

  • restaurants = [[1, 4, 1, 40, 10], [2, 8, 0, 50, 5], [3, 8, 1, 30, 4], [4, 10, 0, 10, 3], [5, 10, 1, 15, 1]]
  • veganFriendly = 1
  • maxPrice = 20
  • maxDistance = 10

Initial List of Restaurants

[ID, Rating, VeganFriendly, Price, Distance]

  1. [1, 4, 1, 40, 10]
  2. [2, 8, 0, 50, 5]
  3. [3, 8, 1, 30, 4]
  4. [4, 10, 0, 10, 3]
  5. [5, 10, 1, 15, 1]

Step 1: Sort Restaurants

First, we sort the list by rating, and for those with the same rating, by ID. In descending order by rating and ID:

  • Sort result: [4, 10, 0, 10, 3], [5, 10, 1, 15, 1], [2, 8, 0, 50, 5], [3, 8, 1, 30, 4], [1, 4, 1, 40, 10]

Step 2: Filter Based on Vegan Friendly, Max Price, and Max Distance

Next, we filter by the vegan-friendly requirement, price, and distance. Since veganFriendly is 1, we only select the restaurants where veganFriendly_i is also 1. Then, we ensure price_i is less than or equal to maxPrice and distance_i is less than or equal to maxDistance.

  • Restaurant 1: Fails (veganFriendly = 1, but Price = 40 (> 20))
  • Restaurant 2: Fails (VeganFriendly = 0)
  • Restaurant 3: Fails (Price = 30 (> 20))
  • Restaurant 4: Fails (VeganFriendly = 0)
  • Restaurant 5: Passes (Rating = 10, VeganFriendly = 1, Price = 15 (<= 20), Distance = 1 (<= 10))

Step 3: Return Result

The final list of restaurant IDs that meet all the criteria is:

  • [5]

Thus, after following steps 1 and 2, our filtered and sorted list of restaurant IDs is [5], which is the answer to our problem. This is the array we would return.

Solution Implementation

1from typing import List
2
3class Solution:
4    def filterRestaurants(
5        self,
6        restaurants: List[List[int]],
7        vegan_friendly: int,
8        max_price: int,
9        max_distance: int,
10    ) -> List[int]:
11        # Sort the restaurants list first by rating in descending order
12        # then by restaurant id, also in descending order in case of ties in ratings.
13        restaurants.sort(key=lambda restaurant: (-restaurant[1], -restaurant[0]))
14      
15        # Initialize an empty list to hold the filtered restaurant ids
16        filtered_restaurant_ids = []
17      
18        # Iterate over the sorted restaurants list
19        for restaurant_id, _, is_vegan, price, distance in restaurants:
20            # Apply the filters:
21            # 1. Check if the restaurant's vegan-friendliness meets the requirement (0 or 1)
22            # 2. Ensure the price does not exceed the max price
23            # 3. Ensure the distance does not exceed the max distance
24            if is_vegan >= vegan_friendly and price <= max_price and distance <= max_distance:
25                # If the restaurant meets all conditions, add its id to the filtered list.
26                filtered_restaurant_ids.append(restaurant_id)
27          
28        # Return the finalized list of restaurant ids that meet all the specified criteria
29        return filtered_restaurant_ids
30
31# Example usage:
32# solution_instance = Solution()
33# result = solution_instance.filterRestaurants([[1,4,1,40,10], [2,8,0,50,5], ...], 1, 50, 10)
34# print(result) would print out the list of restaurant IDs that satisfy the input criteria.
35
1import java.util.*;
2
3class Solution {
4    public List<Integer> filterRestaurants(
5        int[][] restaurants, int veganFriendly, int maxPrice, int maxDistance) {
6      
7        // Sort the array of restaurants based on their ratings in descending order
8        // If the ratings are the same, sort based on the restaurant IDs in descending order
9        Arrays.sort(restaurants, (restaurant1, restaurant2) -> {
10            if (restaurant1[1] == restaurant2[1])
11                return restaurant2[0] - restaurant1[0]; // Sort by ID if ratings are equal
12            else
13                return restaurant2[1] - restaurant1[1]; // Sort by Rating
14        });
15      
16        // Initialize a list to store the IDs of restaurants that satisfy the conditions
17        List<Integer> filteredRestaurants = new ArrayList<>();
18      
19        // Iterate through the sorted array of restaurants
20        for (int[] restaurant : restaurants) {
21            // Check if the restaurant satisfies the conditions for vegan-friendly, max price and max distance
22            if (restaurant[2] >= veganFriendly && restaurant[3] <= maxPrice && restaurant[4] <= maxDistance) {
23                // Add the restaurant ID to the list
24                filteredRestaurants.add(restaurant[0]);
25            }
26        }
27      
28        // Return the list of filtered restaurant IDs
29        return filteredRestaurants;
30    }
31}
32
1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6    // Rewritten function that filters restaurants by given criteria.
7    std::vector<int> filterRestaurants(std::vector<std::vector<int>>& restaurants, int veganFriendly, int maxPrice, int maxDistance) {
8        // Use std::sort with a custom comparison function to sort restaurants
9        // Highest rating first, then by ID if ratings are the same.   
10        std::sort(restaurants.begin(), restaurants.end(), [](const std::vector<int>& a, const std::vector<int>& b) {
11            // First, compare based on ratings.
12            if (a[1] != b[1]) {
13                return a[1] > b[1]; // Return true if 'a' has a higher rating than 'b'.
14            }
15            // If ratings are the same, compare based on ID.
16            return a[0] > b[0]; // Return true if 'a' has a greater ID than 'b'.
17        });
18
19        // Initialize an empty vector to store the IDs of the filtered restaurants.
20        std::vector<int> filteredRestaurants;
21
22        // Loop through all the restaurants.
23        for (auto& restaurant : restaurants) {
24            // Check if each restaurant meets the criteria:
25            // 1. Vegan-friendly (if required),
26            // 2. Price does not exceed maxPrice,
27            // 3. Distance does not exceed maxDistance.
28            if ((veganFriendly == 0 || restaurant[2] == 1) && restaurant[3] <= maxPrice && restaurant[4] <= maxDistance) {
29                filteredRestaurants.push_back(restaurant[0]); // Add the restaurant's ID to the filtered list.
30            }
31        }
32
33        // Return the list of restaurant IDs that meet the criteria.
34        return filteredRestaurants;
35    }
36};
37
1function filterRestaurants(
2    restaurants: number[][], // Array of restaurant details; each restaurant is an array of [id, rating, veganFriendly, price, distance]
3    veganFriendly: number,   // Filter flag for vegan-friendly restaurants (1 for vegan friendly, 0 otherwise)
4    maxPrice: number,        // Maximum acceptable price for filtering
5    maxDistance: number      // Maximum acceptable distance for filtering
6): number[] {
7    // Sort the restaurants first by rating descending, then by id descending in case of a tie on rating
8    restaurants.sort((restaurantA, restaurantB) => {
9        const ratingA = restaurantA[1];
10        const ratingB = restaurantB[1];
11        const idA = restaurantA[0];
12        const idB = restaurantB[0];
13
14        // If ratings are equal, sort by ID; otherwise sort by rating
15        if (ratingA === ratingB) {
16            return idB - idA; // for tie on ratings, higher ID comes first
17        } else {
18            return ratingB - ratingA; // higher rating comes first
19        }
20    });
21
22    const filteredRestaurantIds: number[] = []; // Array to store the IDs of restaurants that meet the filter criteria
23
24    // Iterate through each restaurant to apply filtration based on the given criteria
25    for (const [id, , vegan, price, distance] of restaurants) {
26        // Check if each restaurant meets all the filter conditions
27        if (vegan >= veganFriendly && price <= maxPrice && distance <= maxDistance) {
28            filteredRestaurantIds.push(id); // Add restaurant ID to the result if it meets the criteria
29        }
30    }
31
32    return filteredRestaurantIds; // Return the array containing IDs of filtered restaurants
33}
34
Not Sure What to Study? Take the 2-min Quiz：

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?

Time and Space Complexity

Time Complexity

The time complexity of the provided solution primarily depends on the sorting operation and the subsequent filtering of the restaurants list based on the specified conditions.

  • Sorting: The sort() function is used, which generally has a time complexity of O(n log n), where n is the number of restaurants.
  • Filtering: The for loop iterates over each restaurant, performing constant-time checks (if conditions) for each. This gives us O(n).

The overall time complexity combines the above operations, where sorting dominates, resulting in O(n log n) + O(n). Since the O(n log n) term is the dominant factor, the overall time complexity simplifies to O(n log n).

Space Complexity

The space complexity of the solution involves the storage required for the sorted list and the answer list.

  • Sorted List: The in-place sort() method is used, so it does not require additional space apart from the input list. Hence, the space required remains O(1) as an auxiliary space.
  • Answer List: In the worst case, all restaurants might satisfy the given conditions, so the ans list could contain all restaurant IDs. Therefore, the space complexity for the ans list is O(n).

Taking both into consideration, the overall space complexity of the solution is O(n), where n is the number of restaurants.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?

Recommended Readings

Sorting Summary

Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫