Filter Restaurants by Vegan-Friendly, Price and Distance

Filter Restaurants by Vegan-Friendly, Price and Distance - Problem

Array Sorting Medium

Given an array restaurants where restaurants[i] = [id_i, rating_i, veganFriendly_i, price_i, distance_i]. You need to filter the restaurants using three filters:

The veganFriendly filter will be either true (meaning you should only include restaurants with veganFriendly_i set to true) or false (meaning you can include any restaurant).

In addition, you have the filters maxPrice and maxDistance which are the maximum values 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, veganFriendly_i and veganFriendly take value 1 when true, and 0 when false.

Input & Output

Example 1 — Basic Filtering

$ 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]

💡 Note: Filter vegan-friendly restaurants: [1,4,1,40,10], [3,8,1,30,4], [5,1,1,15,1]. Sort by rating desc then id desc: rating 8 (id=3), rating 4 (id=1), rating 1 (id=5) → [3,1,5]

Example 2 — No Vegan Filter

$ 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]

💡 Note: Include all restaurants within price/distance limits. Sort by rating desc then id desc: rating 10 (id=4), rating 8 (id=3,2 → 3>2), rating 4 (id=1), rating 1 (id=5)

Example 3 — Strict Distance Filter

$ Input: restaurants = [[1,4,1,40,10],[2,8,0,50,5],[3,8,1,30,4]], veganFriendly = 0, maxPrice = 50, maxDistance = 3

› Output: []

💡 Note: No restaurants within distance 3 (minimum distance is 4), so return empty array

Constraints

1 ≤ restaurants.length ≤ 10⁴
restaurants[i].length == 5
1 ≤ id_i, rating_i, price_i, distance_i ≤ 10⁵
1 ≤ maxPrice, maxDistance ≤ 10⁵
veganFriendly_i and veganFriendly are 0 or 1

Visualization

Tap to expand

Understanding the Visualization

Input

Array of restaurants with [id, rating, vegan, price, distance]

Filter

Apply vegan-friendly, price and distance constraints

Sort

Sort by rating desc, then by id desc

Output

Return array of restaurant IDs

Key Takeaway

🎯 Key Insight: Combine multiple filter conditions and use custom comparator for multi-level sorting

Asked in

D DoorDash 25 U Uber 20 a Amazon 15

Filter restaurants by vegan preference, price and distance, then sort by rating descending, then ID descending. The key insight is combining multiple filter conditions with custom sorting comparator. Best approach uses built-in sort with lambda function. Time: O(n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Built-in Filter and Sort	O(n log n)	O(n)	Use built-in filtering and sorting with custom comparator
Brute Force Filter and Sort	O(n²)	O(n)	Filter restaurants manually, then sort using nested loops

Built-in Filter and Sort — Algorithm Steps

Step 1: Filter restaurants in one pass using all conditions
Step 2: Use built-in sort with custom comparator for rating (desc) then id (desc)
Step 3: Extract IDs from sorted restaurants

Visualization

Tap to expand

Step-by-Step Walkthrough

Filter

Single pass to filter restaurants by all conditions

Sort

Use built-in sort with custom comparator

Extract

Extract IDs from sorted results

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int id;
    int rating;
} FilteredRestaurant;

int compare(const void* a, const void* b) {
    FilteredRestaurant* ra = (FilteredRestaurant*)a;
    FilteredRestaurant* rb = (FilteredRestaurant*)b;
    
    if (rb->rating != ra->rating) {
        return rb->rating - ra->rating; // rating desc
    }
    return rb->id - ra->id; // id desc
}

int* solution(int restaurants[][5], int restaurantsSize, int veganFriendly, int maxPrice, int maxDistance, int* returnSize) {
    FilteredRestaurant* filtered = (FilteredRestaurant*)malloc(restaurantsSize * sizeof(FilteredRestaurant));
    int filteredCount = 0;
    
    // Filter restaurants
    for (int i = 0; i < restaurantsSize; i++) {
        int id = restaurants[i][0], rating = restaurants[i][1], vegan = restaurants[i][2];
        int price = restaurants[i][3], distance = restaurants[i][4];
        
        if (veganFriendly == 1 && vegan == 0) continue;
        if (price > maxPrice || distance > maxDistance) continue;
        
        filtered[filteredCount].id = id;
        filtered[filteredCount].rating = rating;
        filteredCount++;
    }
    
    // Sort using built-in qsort
    qsort(filtered, filteredCount, sizeof(FilteredRestaurant), compare);
    
    int* result = (int*)malloc(filteredCount * sizeof(int));
    for (int i = 0; i < filteredCount; i++) {
        result[i] = filtered[i].id;
    }
    
    *returnSize = filteredCount;
    free(filtered);
    return result;
}

int main() {
    // Simplified input parsing for demonstration
    int restaurants[100][5];
    int restaurantsSize = 0;
    
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int veganFriendly, maxPrice, maxDistance;
    scanf("%d %d %d", &veganFriendly, &maxPrice, &maxDistance);
    
    int returnSize;
    int* result = solution(restaurants, restaurantsSize, veganFriendly, maxPrice, maxDistance, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("%d", result[i]);
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

O(n) to filter + O(n log n) for efficient built-in sorting

⚡ Linearithmic

Space Complexity

O(n)

Array to store filtered restaurants and result IDs

⚡ Linearithmic Space

15.2K Views

Medium Frequency

~15 min Avg. Time

489 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Built-in Filter and Sort — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler