Most Beautiful Item for Each Query — Medium Problem & Solution

items[i] = [price, beauty] describes one item in the CodeKairo store.

Difficulty: Medium
Topics: Arrays, Sorting, Binary Search
Asked at: Amazon, Google, 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^5
items[i].length == 2
1 <= price, beauty, queries[j] <= 10^9

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 first i + 1 items.
For each query, binary search the last index whose price is at most the budget.
Answer best[at], or 0 if 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 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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue