Most Beautiful Items for Each Query
Problem
You are given items where each item is a [price, beauty] pair, and a list of queries. For every query value, return the greatest beauty among all items whose price is at most that query; if no item is affordable, the answer for that query is 0. Sort items by price, build a running prefix-max of beauty, then binary search each query for the last affordable item.
items = [[1,2],[3,2],[2,4],[5,6],[3,5]], queries = [1,2,3,4,5,6][2, 4, 5, 5, 6, 6]def maximum_beauty(items, queries):
items.sort(key=lambda it: it[0])
prices, best = [], []
cur = 0
for price, beauty in items:
cur = max(cur, beauty)
prices.append(price)
best.append(cur)
out = []
for q in queries:
lo, hi = 0, len(prices)
while lo < hi:
mid = (lo + hi) // 2
if prices[mid] <= q:
lo = mid + 1
else:
hi = mid
out.append(best[lo - 1] if lo > 0 else 0)
return outfunction maximumBeauty(items, queries) {
items.sort((a, b) => a[0] - b[0]);
const prices = [], best = [];
let cur = 0;
for (const [price, beauty] of items) {
cur = Math.max(cur, beauty);
prices.push(price);
best.push(cur);
}
return queries.map(q => {
let lo = 0, hi = prices.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (prices[mid] <= q) lo = mid + 1;
else hi = mid;
}
return lo > 0 ? best[lo - 1] : 0;
});
}class Solution {
public int[] maximumBeauty(int[][] items, int[] queries) {
Arrays.sort(items, (a, b) -> a[0] - b[0]);
int n = items.length;
int[] prices = new int[n], best = new int[n];
int cur = 0;
for (int i = 0; i < n; i++) {
cur = Math.max(cur, items[i][1]);
prices[i] = items[i][0];
best[i] = cur;
}
int[] out = new int[queries.length];
for (int i = 0; i < queries.length; i++) {
int lo = 0, hi = n;
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (prices[mid] <= queries[i]) lo = mid + 1;
else hi = mid;
}
out[i] = lo > 0 ? best[lo - 1] : 0;
}
return out;
}
}vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {
sort(items.begin(), items.end());
int n = items.size();
vector<int> prices(n), best(n);
int cur = 0;
for (int i = 0; i < n; i++) {
cur = max(cur, items[i][1]);
prices[i] = items[i][0];
best[i] = cur;
}
vector<int> out(queries.size());
for (int i = 0; i < (int)queries.size(); i++) {
int lo = 0, hi = n;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (prices[mid] <= queries[i]) lo = mid + 1;
else hi = mid;
}
out[i] = lo > 0 ? best[lo - 1] : 0;
}
return out;
}Explanation
For each query we want the most beautiful item we can afford — that is, the largest beauty among items whose price is no more than the query. Scanning every item for every query would be slow, so we do the heavy work once and then answer each query with a fast lookup.
First we sort the items by price. Now items are lined up from cheapest to most expensive. The clever part is the prefix-max of beauty: as we walk left to right, we keep a running maximum so that best[i] holds the best beauty among the first i + 1 items. Because the array is sorted by price, every item from the start up to position i is affordable for any budget at least as large as prices[i].
With that table ready, a query becomes a single binary search. We find the rightmost item whose price is <= q; call its index lo - 1. The answer is just best[lo - 1], the prefix-max beauty up to that affordable item. If no item is affordable (lo == 0), the answer is 0.
Example: items = [[1,2],[3,2],[2,4],[5,6],[3,5]]. Sorted by price gives prices [1, 2, 3, 3, 5] with prefix-max beauty [2, 4, 4, 5, 6]. For query 3, the last price <= 3 sits at index 3, so the answer is best[3] = 5. For query 5 it is best[4] = 6.
Sorting costs n log n once, and each of the q queries does an O(log n) binary search, which is far faster than re-scanning the items every time.