Most Beautiful Item for Each Query

Medium
966.

Most Beautiful Item for Each Query

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.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} items
 * @param {number[]} queries
 * @return {number[]}
 */
var maximumBeauty = function(items, queries) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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

Hints for Most Beautiful Item for Each Query

  1. Hint 1

    Sort the items by price.

  2. Hint 2

    Then the answer to a query is a prefix maximum of beauty over that sorted list.

  3. 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

  1. Sort the items ascending by price.
  2. Build best[i] = the largest beauty among the first i + 1 items.
  3. For each query, binary search the last index whose price is at most the budget.
  4. 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

Java

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