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

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

✓ Brute Force Filter and Sort

⏱️ Time: O(n²) Space: O(n)

Iterate through all restaurants, apply filters manually, collect valid ones, then use nested loops to sort by rating and id.

Built-in Filter and Sort

⏱️ Time: O(n log n) Space: O(n)

Filter restaurants using a single pass, then use built-in sort with custom comparator for multi-level sorting by rating and id.

Brute Force Filter and Sort — Algorithm Steps

Step 1: Iterate through restaurants and manually check each filter condition
Step 2: Collect IDs of restaurants that pass all filters
Step 3: Use nested loops to sort by rating (desc) then by id (desc)

Visualization

Tap to expand

Step-by-Step Walkthrough

Filter

Check each restaurant against all conditions

Collect

Store valid restaurant IDs and ratings

Sort

Use nested loops to sort by rating then ID

Code -

solution.c — C

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

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

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++;
    }
    
    // Manual sorting using nested loops
    for (int i = 0; i < filteredCount; i++) {
        for (int j = 0; j < filteredCount - i - 1; j++) {
            if (filtered[j].rating < filtered[j + 1].rating ||
                (filtered[j].rating == filtered[j + 1].rating && filtered[j].id < filtered[j + 1].id)) {
                FilteredRestaurant temp = filtered[j];
                filtered[j] = filtered[j + 1];
                filtered[j + 1] = temp;
            }
        }
    }
    
    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() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse restaurants array
    static int restaurants[1000][5];
    int restaurantsSize = 0;
    
    // Find the start of the array
    char* p = line;
    while (*p && *p != '[') p++;
    if (*p == '[') p++; // Skip first '['
    
    // Parse each restaurant
    while (*p && *p != ']') {
        // Skip whitespace and commas
        while (*p && (*p == ' ' || *p == ',' || *p == '\n')) p++;
        
        if (*p == '[') {
            p++; // Skip '['
            // Parse 5 numbers for this restaurant
            for (int i = 0; i < 5; i++) {
                // Skip whitespace
                while (*p && (*p == ' ' || *p == '\t')) p++;
                
                // Parse number
                int num = 0;
                int sign = 1;
                if (*p == '-') {
                    sign = -1;
                    p++;
                }
                while (*p && isdigit(*p)) {
                    num = num * 10 + (*p - '0');
                    p++;
                }
                restaurants[restaurantsSize][i] = sign * num;
                
                // Skip comma and whitespace
                while (*p && (*p == ',' || *p == ' ' || *p == '\t')) p++;
            }
            
            // Skip closing ']'
            while (*p && *p != ']') p++;
            if (*p == ']') p++;
            
            restaurantsSize++;
        } else if (*p == ']') {
            break;
        } else {
            p++;
        }
    }
    
    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²)

O(n) to filter + O(n²) for nested loop sorting

⚠ Quadratic Growth

Space Complexity

O(n)

Array to store filtered restaurant data 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

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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Filter and Sort — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler