1333. Filter Restaurants Vegan-Friendly Price Distance

The problem

Given the array restaurants where restaurants[i] = [id_i, rating_i, veganFriendly_i, price_i, distance_i]. You have 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 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 veganFriendly_i 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 <= id_i, rating_i, price_i, distance_i<= 10^5
1 <= maxPrice, maxDistance <= 10^5
veganFriendly_i and veganFriendly are 0 or 1.
All id_i are distinct.

Approach overview

Problem Overview: You receive a list of restaurants where each entry contains id, rating, veganFriendly, price, and distance. Your task is to filter restaurants based on vegan preference, maximum price, and maximum distance, then return the remaining restaurant IDs sorted by rating (descending) and id (descending).

Approach 1: Simple Filtering and Sorting (O(n log n) time, O(n) space)

Scan the input array and filter out restaurants that do not satisfy the constraints. If veganFriendly = 1, only keep restaurants with the vegan flag set. Also discard any restaurant where price > maxPrice or distance > maxDistance. Store the valid restaurants in a temporary list.

Next, sort this filtered list by two keys: rating in descending order and id in descending order. Most languages support custom comparators or tuple-based sorting, which makes this step straightforward. After sorting, iterate through the list and collect only the restaurant IDs.

This approach works well because filtering is linear and sorting dominates the runtime at O(n log n). The implementation is short and easy to reason about, making it the most common solution for problems involving array processing combined with sorting.

Approach 2: Using Priority Queue (Heap) (O(n log n) time, O(n) space)

Instead of sorting the entire filtered list at the end, push valid restaurants into a max-heap ordered by rating first and id second. While iterating through the restaurants, apply the same filtering conditions and insert qualifying entries into the heap.

Once all valid restaurants are in the heap, repeatedly pop the top element to retrieve restaurants in the correct order. Each insertion and removal costs O(log n), so building and draining the heap leads to O(n log n) time overall. This method highlights the use of a heap when ordered extraction is required.

Recommended for interviews: The filtering + sorting approach is what most interviewers expect. It demonstrates that you can apply constraints with a linear scan and then use a custom comparator to enforce multi-key ordering. The heap solution is also valid but adds unnecessary complexity unless the problem specifically requires incremental retrieval.

Approach 1: Simple Filtering and Sorting

This approach involves iterating through each restaurant and checking if it fulfills the given conditions: vegan friendliness, price within the maximum limit, and distance within the maximum limit. After filtering, the resulting list of restaurants is sorted first by rating in descending order and then by ID in descending order.

Python

def filterRestaurants(restaurants, veganFriendly, maxPrice, maxDistance):
    filtered = [r for r in restaurants if (veganFriendly == 0 or r[2] == 1) and r[3] <= maxPrice and r[4] <= maxDistance]
    filtered.sort(key=lambda x: (-x[1], -x[0]))
    return [r[0] for r in filtered]

Java

import java.util.*;

class Restaurant {
    int id, rating, veganFriendly, price, distance;
    public Restaurant(int id, int rating, int veganFriendly, int price, int distance) {
        this.id = id;
        this.rating = rating;
        this.veganFriendly = veganFriendly;
        this.price = price;
        this.distance = distance;
    }
}

class Solution {
    public List<Integer> filterRestaurants(int[][] restaurants, int veganFriendly, int maxPrice, int maxDistance) {
        List<Restaurant> filtered = new ArrayList<>();
        for (int[] rest : restaurants) {
            if ((veganFriendly == 0 || rest[2] == 1) && rest[3] <= maxPrice && rest[4] <= maxDistance) {
                filtered.add(new Restaurant(rest[0], rest[1], rest[2], rest[3], rest[4]));
            }
        }
        filtered.sort((a, b) -> {
            if (b.rating != a.rating) return b.rating - a.rating;
            return b.id - a.id;
        });
        List<Integer> result = new ArrayList<>();
        for (Restaurant rest : filtered) {
            result.add(rest.id);
        }
        return result;
    }
}

C++

#include <vector>
#include <algorithm>
using namespace std;

vector<int> filterRestaurants(vector<vector<int>>& restaurants, int veganFriendly, int maxPrice, int maxDistance) {
    vector<vector<int>> filtered;
    for (auto& rest : restaurants) {
        if ((veganFriendly == 0 || rest[2] == 1) && rest[3] <= maxPrice && rest[4] <= maxDistance) {
            filtered.push_back(rest);
        }
    }
    sort(filtered.begin(), filtered.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> result;
    for (auto& rest : filtered) {
        result.push_back(rest[0]);
    }
    return result;
}

JavaScript

function filterRestaurants(restaurants, veganFriendly, maxPrice, maxDistance) {
    return restaurants
        .filter(r => (veganFriendly === 0 || r[2] === 1) && r[3] <= maxPrice && r[4] <= maxDistance)
        .sort((a, b) => b[1] - a[1] || b[0] - a[0])
        .map(r => r[0]);
}

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

typedef struct {
    int id;
    int rating;
    int veganFriendly;
    int price;
    int distance;
} Restaurant;

int compare(const void *a, const void *b) {
    Restaurant *restA = (Restaurant *)a;
    Restaurant *restB = (Restaurant *)b;
    if (restA->rating != restB->rating)
        return restB->rating - restA->rating;
    return restB->id - restA->id;
}

int* filterRestaurants(int** restaurants, int restaurantsSize, int* restaurantsColSize, int veganFriendly, int maxPrice, int maxDistance, int* returnSize) {
    Restaurant filtered[restaurantsSize];
    int count = 0;
    for (int i = 0; i < restaurantsSize; ++i) {
        int *rest = restaurants[i];
        if ((veganFriendly == 0 || rest[2] == 1) && rest[3] <= maxPrice && rest[4] <= maxDistance) {
            filtered[count].id = rest[0];
            filtered[count].rating = rest[1];
            filtered[count].veganFriendly = rest[2];
            filtered[count].price = rest[3];
            filtered[count].distance = rest[4];
            count++;
        }
    }
    qsort(filtered, count, sizeof(Restaurant), compare);
    int* result = (int*)malloc(sizeof(int) * count);
    for (int i = 0; i < count; ++i) {
        result[i] = filtered[i].id;
    }
    *returnSize = count;
    return result;
}

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public IList<int> FilterRestaurants(int[][] restaurants, int veganFriendly, int maxPrice, int maxDistance) {
        var filtered = new List<int[]>();
        foreach (var rest in restaurants) {
            if ((veganFriendly == 0 || rest[2] == 1) && rest[3] <= maxPrice && rest[4] <= maxDistance) {
                filtered.Add(rest);
            }
        }
        var sortedFiltered = filtered.OrderByDescending(r => r[1]).ThenByDescending(r => r[0]).ToList();
        return sortedFiltered.Select(r => r[0]).ToList();
    }
}

This Python solution uses a list comprehension to filter restaurants based on the vegan-friendly status, maximum price, and maximum distance. After obtaining the filtered list, we call `sort()` with a custom key that orders by descending rating and descending ID in the case of ties.

The final list of IDs represents the filtered and sorted restaurants.

Complexity

Time Complexity: O(n log n) for sorting operation.

Space Complexity: O(n), used for the filtered subset of restaurants.

Try this approach in the editor

Approach 2: Using Priority Queue (Heap)

This approach makes use of a priority queue (often implemented as a min-heap) to filter and sort items efficiently. As we traverse through the list of restaurants, each is evaluated against criteria and added to the priority queue. When the heap size exceeds the needed capacity, the smallest element (in terms of our sorting requirements) is expelled, ensuring only the top items by our criteria remain.

Java

import java.util.*;

class Solution {
    public List<Integer> filterRestaurants(int[][] restaurants, int veganFriendly, int maxPrice, int maxDistance) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
            if (a[1] != b[1]) return Integer.compare(b[1], a[1]);
            return Integer.compare(b[0], a[0]);
        });
        
        for (int[] rest : restaurants) {
            if ((veganFriendly == 0 || rest[2] == 1) && rest[3] <= maxPrice && rest[4] <= maxDistance) {
                pq.offer(rest);
            }
        }
        
        List<Integer> result = new ArrayList<>();
        while (!pq.isEmpty()) {
            result.add(pq.poll()[0]);
        }
        return result;
    }
}

C++

#include <vector>
#include <queue>
using namespace std;

vector<int> filterRestaurants(vector<vector<int>>& restaurants, int veganFriendly, int maxPrice, int maxDistance) {
    auto comp = [](const vector<int>& a, const vector<int>& b) {
        if (a[1] != b[1]) return a[1] < b[1];
        return a[0] < b[0];
    };
    priority_queue<vector<int>, vector<vector<int>>, decltype(comp)> pq(comp);

    for (auto& rest : restaurants) {
        if ((veganFriendly == 0 || rest[2] == 1) && rest[3] <= maxPrice && rest[4] <= maxDistance) {
            pq.push(rest);
        }
    }

    vector<int> result;
    while (!pq.empty()) {
        result.push_back(pq.top()[0]);
        pq.pop();
    }
    return result;
}

In this Java variant, we utilize a priority queue to keep track of the top restaurant entries dynamically. This is achieved using a comparator that enforces order by descending rating and ID.

The collection of filtered restaurants is managed within the priority queue, which ensures only the highest-ranking items according to criteria are processed into the final sorted list of IDs.

Complexity

Time Complexity: O(n log n), due to the necessity of maintaining heap order in priority queue as elements are added.

Space Complexity: O(n), needed to store restaurants in the priority queue.

Try this approach in the editor

Approach 3: Default Approach

TypeScript

function filterRestaurants(
    restaurants: number[][],
    veganFriendly: number,
    maxPrice: number,
    maxDistance: number,
): number[] {
    restaurants.sort((a, b) => (a[1] === b[1] ? b[0] - a[0] : b[1] - a[1]));
    const ans: number[] = [];
    for (const [id, _, vegan, price, distance] of restaurants) {
        if (vegan >= veganFriendly && price <= maxPrice && distance <= maxDistance) {
            ans.push(id);
        }
    }
    return ans;
}

func filterRestaurants(restaurants [][]int, veganFriendly int, maxPrice int, maxDistance int) (ans []int) {
	sort.Slice(restaurants, func(i, j int) bool {
		a, b := restaurants[i], restaurants[j]
		if a[1] != b[1] {
			return a[1] > b[1]
		}
		return a[0] > b[0]
	})
	for _, r := range restaurants {
		if r[2] >= veganFriendly && r[3] <= maxPrice && r[4] <= maxDistance {
			ans = append(ans, r[0])
		}
	}
	return
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Simple Filtering and Sorting	Time Complexity: O(n log n) for sorting operation. Space Complexity: O(n), used for the filtered subset of restaurants.
Using Priority Queue (Heap)	Time Complexity: O(n log n), due to the necessity of maintaining heap order in priority queue as elements are added. Space Complexity: O(n), needed to store restaurants in the priority queue.
Default Approach	–

Approach

Complexity

Simple Filtering and Sorting

Time Complexity: O(n log n) for sorting operation.

Space Complexity: O(n), used for the filtered subset of restaurants.

Using Priority Queue (Heap)

Time Complexity: O(n log n), due to the necessity of maintaining heap order in priority queue as elements are added.

Space Complexity: O(n), needed to store restaurants in the priority queue.

Default Approach

–

Complexity analysis

Approach	Time	Space	When to Use
Simple Filtering and Sorting	O(n log n)	O(n)	Best general solution when you can filter first and then sort by multiple fields.
Priority Queue (Heap)	O(n log n)	O(n)	Useful when you need ordered extraction or streaming results instead of sorting once.

Frequently asked questions

Is Filter Restaurants by Vegan-Friendly, Price and Distance easy or hard?

The problem is rated Medium because it requires combining conditional filtering with multi-criteria sorting. The algorithm itself is straightforward, but candidates must correctly apply the constraints and comparator ordering.

Filter Restaurants by Vegan-Friendly, Price and Distance Python/Java solution

In Python, filter the list using a list comprehension and sort with a custom key like (-rating, -id). In Java, iterate through the array, store valid restaurants in a list, and call Collections.sort with a comparator that orders by rating descending then id descending.

How to solve Filter Restaurants by Vegan-Friendly, Price and Distance in O(n)?

A strict O(n) solution is not practical because the final output must be ordered by rating and id. Any comparison-based ordering requires sorting or heap operations, leading to O(n log n) time in the general case. Filtering alone is O(n), but ordering introduces the log n factor.

What is the best approach for Filter Restaurants by Vegan-Friendly, Price and Distance?

The most practical solution filters restaurants using the given constraints and then sorts the remaining entries by rating and id in descending order. Filtering takes O(n) time and sorting takes O(n log n), which dominates the runtime. This approach is concise and directly maps to the problem requirements.

Is Filter Restaurants by Vegan-Friendly, Price and Distance asked at Google/Amazon/Meta?

Problems combining filtering with custom sorting appear frequently in interviews at companies like Amazon, Google, and Meta. Interviewers use them to evaluate how you process arrays, apply constraints, and implement multi-key sorting logic.

What data structure is used in Filter Restaurants by Vegan-Friendly, Price and Distance?

The primary data structures are arrays or lists to store the restaurants and the filtered results. Sorting utilities with custom comparators are used to order the results. An alternative solution uses a priority queue (max-heap) to retrieve restaurants by rating and id order.

What is the time complexity of Filter Restaurants by Vegan-Friendly, Price and Distance?

The typical solution runs in O(n log n) time. You first scan the array once to filter valid restaurants in O(n), then sort the filtered results by rating and id which costs O(n log n). Space complexity is O(n) to store the filtered list.

Filter Restaurants by Vegan-Friendly, Price and Distance solution and explanation

The problem

Approach overview

Approach 1: Simple Filtering and Sorting

Approach 2: Using Priority Queue (Heap)

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Filter Restaurants by Vegan-Friendly, Price and Distance solution and explanation

The problem

Approach overview

Approach 1: Simple Filtering and Sorting

Approach 2: Using Priority Queue (Heap)

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems