Filter Restaurants by Vegan-Friendly, Price and Distance Leetcode Solution

Difficulty Level Medium
Frequently asked in Amazon YelpViews 1706

Problem Statement

Filter Restaurants by Vegan-Friendly, Price, and Distance Leetcode Solution – 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 it 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

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).

 

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.

Approach

Idea:

The main idea is to first sort the list of restaurants by the ratings, if ratings are the same then by id. For this, we can build our own custom comparator function.

Now, that we have sorted the restaurants, we can insert the id’s of valid restaurants into another vector and return it.

Code

C++ Code for Filter Restaurants by Vegan-Friendly, Price and Distance

class Solution {
public:
    vector<int> filterRestaurants(vector<vector<int>>& restaurants, int veganFriendly, int maxPrice, int maxDistance) {
        int n = restaurants.size();
        
        //Firstly sort on the basis of the condition given.
        sort(restaurants.begin(),restaurants.end(),[](vector<int> &a,vector<int> &b){
            if(a[1] == b[1]){
                return a[0] > b[0];
            } 
            return a[1] > b[1];
        });
        
        vector<int> id;
        //Then, insert the ids of valid restaurants in the result vector.
        for(auto vc : restaurants){
            if(veganFriendly==1 && vc[2]!=1){continue;}
            if(vc[3]>maxPrice){continue;}
            if(vc[4]>maxDistance){continue;}
            
            id.push_back(vc[0]);
        }
        
        return id;
    }
};

Java Code for Filter Restaurants by Vegan-Friendly, Price and Distance

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> result = new ArrayList<>();
        for(int[] arr: restaurants) {
            if((veganFriendly == arr[2] || veganFriendly == 0) 
              && maxPrice >= arr[3] && maxDistance >= arr[4]) {
                result.add(arr[0]);
            }
        }
        
        return result;
    }
}

 

Complexity Analysis for Filter Restaurants by Vegan-Friendly, Price and Distance Leetcode Solution

Time Complexity

Sorting the whole list takes O(nlogn) time and picking up the valid id from the sorted list takes another O(n) time, So the overall Complexity is O(n + nlogn) that is O(nlogn).

Space Complexity

We are only using O(k) space, where k denotes the number of valid restaurants since in the worst case k can tend to n. So the overall Space Complexity is O(n).

Translate »