Most beautiful item for each query

Array Binary Search Sorting

62.1% acceptance

Feb 25, 2026

1266

You are given a 2D integer array items where items[i] = [pricei, beautyi] denotes the price and beauty of an item respectively. You are also given a 0-indexed integer array queries. For each queries[j], you want to determine the maximum beauty of an item whose price is less than or equal to queries[j]. If no such item exists, then the answer to this query is 0. Return an array answer of the same length as queries where answer[j] is the answer to the jth query.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_beauty(mut items: Vec<Vec<i32>>, queries: Vec<i32>) -> Vec<i32> {
    items.sort_unstable_by_key(|e| e[0]);
    let m = items.len();
    // Build prefix max of beauty
    let mut prefix_beauty = vec![0i32; m];
    prefix_beauty[0] = items[0][1];
    for i in 1..m {
      prefix_beauty[i] = prefix_beauty[i - 1].max(items[i][1]);
    }
    queries.iter().map(|&q| {
      // Find rightmost item with price <= q
      let pos = items.partition_point(|e| e[0] <= q);
      if pos == 0 { 0 } else { prefix_beauty[pos - 1] }
    }).collect()
  }
}