Most Beautiful Item for Each Query
Most Beautiful Item for Each Query is a medium binary search problem solved with the bisect pattern.
The best approach, optimal (sort + prefix maximum + binary search), runs in O((n + m) log n) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (scan all items per query) up.
Problem
You are given a 2D integer array items where items[i] = [price, beauty] describes one item, and an integer array queries.
For each queries[j], find the largest beauty among all items whose price is at most queries[j]. If no item is that cheap, the answer for that query is 0. Return an array answer with answer[j] for every query.
Examples
Example 1
- Input
items = [[4, 7], [2, 3], [6, 5], [2, 9]], queries = [1, 2, 5, 10]- Output
[0, 9, 9, 9]- Why
- Budget 1 buys nothing. With budget 2 the item [2, 9] is affordable, and nothing more expensive is more beautiful.
Example 2
- Input
items = [[3, 2], [5, 8], [8, 6]], queries = [8, 4, 5]- Output
[8, 2, 8]- Why
- Budget 4 only reaches the item priced 3; budgets 5 and 8 can take the item with beauty 8.
Constraints
1 <= items.length, queries.length <= 10^5items[i].length == 21 <= price, beauty, queries[j] <= 10^9
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (scan all items per query) | O(n · m) | O(1) |
| Optimal (sort + prefix maximum + binary search) | O((n + m) log n) | O(n) |
1Brute force (scan all items per query)
O(n · m)Each of the m queries scans all n items.O(1)Only the output array besides a running maximum.For each query, look at every item and keep the largest beauty among items whose price fits the budget.
- For each query q: best = 0.
- For each item [price, beauty]: if price <= q, best = max(best, beauty).
- Store best as the answer for that query.
class Solution {
public int[] maximumBeauty(int[][] items, int[] queries) {
int[] answer = new int[queries.length];
for (int j = 0; j < queries.length; j++) {
int best = 0;
for (int[] item : items) {
if (item[0] <= queries[j]) best = Math.max(best, item[1]);
}
answer[j] = best;
}
return answer;
}
}class Solution:
def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:
answer = []
for q in queries:
best = 0
for price, beauty in items:
if price <= q:
best = max(best, beauty)
answer.append(best)
return answerclass Solution {
public:
vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {
vector<int> answer(queries.size());
for (size_t j = 0; j < queries.size(); j++) {
int best = 0;
for (auto& item : items) {
if (item[0] <= queries[j]) best = max(best, item[1]);
}
answer[j] = best;
}
return answer;
}
};function maximumBeauty(items, queries) {
const answer = new Array(queries.length);
for (let j = 0; j < queries.length; j++) {
let best = 0;
for (const [price, beauty] of items) {
if (price <= queries[j]) best = Math.max(best, beauty);
}
answer[j] = best;
}
return answer;
}2Optimal (sort + prefix maximum + binary search)
O((n + m) log n)Sorting takes O(n log n) and each of the m queries is one binary search.O(n)The prefix-maximum array (plus the sort's own space).Sort the items by price and turn the beauty column into a running maximum, so best[i] is the most beautiful item among the i + 1 cheapest. For each query, binary search the last item whose price is at most the query; its running maximum is the answer, or 0 if no item is affordable.
- Sort items by price.
- best[i] = max(best[i - 1], beauty of item i).
- For each query q, find the largest index i with price[i] <= q by binary search.
- Answer best[i], or 0 if no such index exists.
class Solution {
public int[] maximumBeauty(int[][] items, int[] queries) {
Arrays.sort(items, (a, b) -> Integer.compare(a[0], b[0]));
int n = items.length;
int[] best = new int[n];
for (int i = 0; i < n; i++) {
best[i] = Math.max(i > 0 ? best[i - 1] : 0, items[i][1]);
}
int[] answer = new int[queries.length];
for (int j = 0; j < queries.length; j++) {
int lo = 0, hi = n - 1, idx = -1;
while (lo <= hi) {
int mid = (lo + hi) >>> 1;
if (items[mid][0] <= queries[j]) {
idx = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
answer[j] = idx == -1 ? 0 : best[idx];
}
return answer;
}
}class Solution:
def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:
items.sort(key=lambda it: it[0])
prices = [p for p, _ in items]
best = []
running = 0
for _, beauty in items:
running = max(running, beauty)
best.append(running)
answer = []
for q in queries:
idx = bisect.bisect_right(prices, q) - 1
answer.append(best[idx] if idx >= 0 else 0)
return answerclass Solution {
public:
vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {
sort(items.begin(), items.end(), [](const vector<int>& a, const vector<int>& b) {
return a[0] < b[0];
});
int n = items.size();
vector<int> best(n);
for (int i = 0; i < n; i++) {
best[i] = max(i > 0 ? best[i - 1] : 0, items[i][1]);
}
vector<int> answer(queries.size());
for (size_t j = 0; j < queries.size(); j++) {
int lo = 0, hi = n - 1, idx = -1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (items[mid][0] <= queries[j]) {
idx = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
answer[j] = idx == -1 ? 0 : best[idx];
}
return answer;
}
};function maximumBeauty(items, queries) {
items.sort((a, b) => a[0] - b[0]);
const n = items.length;
const best = new Array(n);
for (let i = 0; i < n; i++) {
best[i] = Math.max(i > 0 ? best[i - 1] : 0, items[i][1]);
}
const answer = new Array(queries.length);
for (let j = 0; j < queries.length; j++) {
let lo = 0, hi = n - 1, idx = -1;
while (lo <= hi) {
const mid = (lo + hi) >> 1;
if (items[mid][0] <= queries[j]) {
idx = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
answer[j] = idx === -1 ? 0 : best[idx];
}
return answer;
}Edge cases to test
- A query smaller than every price gets 0
- Several items with the same price but different beauty
- A cheaper item can be more beautiful than every pricier one
- Queries are not sorted and may repeat
Hints
Hint 1
For one query, you want the maximum beauty over all items whose price is at most the query. How would you answer it directly?
Hint 2
Sort the items by price. Then the affordable items always form a prefix of the sorted list.
Hint 3
Precompute the running maximum beauty over each prefix, and binary search the last affordable price for every query.
FAQ
What is the best time complexity for Most Beautiful Item for Each Query?
Optimal (sort + prefix maximum + binary search) runs in O((n + m) log n) time and O(n) extra space. Sorting takes O(n log n) and each of the m queries is one binary search.
Which pattern does Most Beautiful Item for Each Query use?
It is a binary search problem that uses the bisect pattern. Other problems with the same pattern: bisect_left, bisect_right, Search Insert Position, Floor in a Sorted Array.
Is there a brute force solution for Most Beautiful Item for Each Query?
Yes. Brute force (scan all items per query) takes O(n · m) time and O(1) space. For each query, look at every item and keep the largest beauty among items whose price fits the budget.
Which edge cases should I test for Most Beautiful Item for Each Query?
A query smaller than every price gets 0; Several items with the same price but different beauty; A cheaper item can be more beautiful than every pricier one; Queries are not sorted and may repeat.