Most Beautiful Item for Each Query — Problem & Solution
Most Beautiful Item for Each Query solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Most Beautiful Item for Each Query is a medium coding problem on arrays, sorting and binary search, asked in Amazon, Google, Razorpay and Walmart interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Binary Search
- Asked at: Amazon, Google, Razorpay, Walmart
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
items[i] = [price, beauty] describes one item in the CodeKairo store. For each queries[j], find the greatest beauty among the items whose price is at most queries[j].
If no item is that cheap, the answer for that query is 0.
Example 1
Input: items = [[1,2],[3,2],[2,4],[5,6],[3,5]], queries = [1,2,3,4,5,6]
Output: [2,4,5,5,6,6]
Example 2
Input: items = [[1,2],[1,2],[1,3],[1,4]], queries = [1]
Output: [4]
Explanation: All four cost 1, so the best beauty is 4.
Example 3
Input: items = [[10,1000]], queries = [5]
Output: [0]
Explanation: Nothing is affordable.
Constraints
1 <= items.length, queries.length <= 10^5items[i].length == 21 <= price, beauty, queries[j] <= 10^9
Hints for Most Beautiful Item for Each Query
Hint 1
Sort the items by price.
Hint 2
Then the answer to a query is a prefix maximum of beauty over that sorted list.
Hint 3
Binary search each query for the last affordable item and read the running maximum there.
How to solve Most Beautiful Item for Each Query
Sort by price and precompute a running maximum of beauty. A query then reduces to finding the last item within budget and reading the running maximum at that position.
Approach
- Sort the items ascending by price.
- Build
best[i]= the largest beauty among the firsti + 1items. - For each query, binary search the last index whose price is at most the budget.
- Answer
best[at], or0if no item qualifies.
Why it works
The running maximum is what makes each query O(log n): the set of affordable items is always a prefix of the sorted list, so the answer never depends on anything but where that prefix ends. Precomputing it once beats re-scanning per query, which would be O(n · q).
Complexity
- Time —
O((n + q) log n) - Space —
O(n)
Pitfalls
- The running maximum must be taken after sorting, not on the original order.
- The comparison is
<=— an item priced exactly at the budget is affordable. - A query below every price answers 0, not the smallest beauty.
Reference solution
Python
from typing import List
import bisect
def maximumBeauty(items: List[List[int]], queries: List[int]) -> List[int]:
ordered = sorted(items, key=lambda it: it[0])
prices = []
best = []
run = 0
for price, beauty in ordered:
run = max(run, beauty)
prices.append(price)
best.append(run)
out = []
for q in queries:
at = bisect.bisect_right(prices, q) - 1
out.append(0 if at < 0 else best[at])
return outJava
public static int[] maximumBeauty(int[][] items, int[] queries) {
int[][] sorted = items.clone();
Arrays.sort(sorted, (a, b) -> a[0] - b[0]);
int[] best = new int[sorted.length];
int run = 0;
for (int i = 0; i < sorted.length; i++) {
run = Math.max(run, sorted[i][1]);
best[i] = run;
}
int[] out = new int[queries.length];
for (int q = 0; q < queries.length; q++) {
int lo = 0, hi = sorted.length - 1, at = -1;
while (lo <= hi) {
int mid = (lo + hi) >>> 1;
if (sorted[mid][0] <= queries[q]) { at = mid; lo = mid + 1; }
else hi = mid - 1;
}
out[q] = at < 0 ? 0 : best[at];
}
return out;
}C++
vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {
vector<vector<int>> sorted = items;
sort(sorted.begin(), sorted.end(), [](const vector<int>& a, const vector<int>& b) { return a[0] < b[0]; });
vector<int> best(sorted.size());
int run = 0;
for (size_t i = 0; i < sorted.size(); i++) {
run = max(run, sorted[i][1]);
best[i] = run;
}
vector<int> out;
for (int q : queries) {
int lo = 0, hi = (int) sorted.size() - 1, at = -1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (sorted[mid][0] <= q) { at = mid; lo = mid + 1; }
else hi = mid - 1;
}
out.push_back(at < 0 ? 0 : best[at]);
}
return out;
}JavaScript
var maximumBeauty = function(items, queries) {
var sorted = items.slice();
sorted.sort(function(a, b) { return a[0] - b[0]; });
var best = [];
var run = 0, i;
for (i = 0; i < sorted.length; i++) {
if (sorted[i][1] > run) run = sorted[i][1];
best.push(run);
}
var out = [];
for (var q = 0; q < queries.length; q++) {
var lo = 0, hi = sorted.length - 1, at = -1;
while (lo <= hi) {
var mid = (lo + hi) >> 1;
if (sorted[mid][0] <= queries[q]) { at = mid; lo = mid + 1; }
else hi = mid - 1;
}
out.push(at < 0 ? 0 : best[at]);
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms