# Most Beautiful Item for Each Query
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/most-beautiful-item-for-each-query)
Canonical: https://scaleengineer.com/dsa/problems/most-beautiful-item-for-each-query
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [razorpay](https://scaleengineer.com/companies/razorpay), [Postmates](https://scaleengineer.com/companies/postmates)
---
## Problem
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_.

**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]
**Explanation:**
- For queries[0]=1, [1,2] is the only item which has price <= 1. Hence, the answer for this query is 2.
- For queries[1]=2, the items which can be considered are [1,2] and [2,4]. 
  The maximum beauty among them is 4.
- For queries[2]=3 and queries[3]=4, the items which can be considered are [1,2], [3,2], [2,4], and [3,5].
  The maximum beauty among them is 5.
- For queries[4]=5 and queries[5]=6, all items can be considered.
  Hence, the answer for them is the maximum beauty of all items, i.e., 6.

**Example 2:**

**Input:** items = [[1,2],[1,2],[1,3],[1,4]], queries = [1]
**Output:** [4]
**Explanation:** 
The price of every item is equal to 1, so we choose the item with the maximum beauty 4. 
Note that multiple items can have the same price and/or beauty.  

**Example 3:**

**Input:** items = [[10,1000]], queries = [5]
**Output:** [0]
**Explanation:**
No item has a price less than or equal to 5, so no item can be chosen.
Hence, the answer to the query is 0.

**Constraints:**

* `1 <= items.length, queries.length <= 105`
* `items[i].length == 2`
* `1 <= pricei, beautyi, queries[j] <= 109`

# Approaches
## Brute Force Iteration
A simple and straightforward approach. For each query, we iterate through all the items. If an item's price is within the query's budget, we consider its beauty. We keep track of the maximum beauty found for each query.
**Time:** O(N * Q), where N is the number of items and Q is the number of queries. For each of the Q queries, we perform a linear scan of N items. · **Space:** O(Q) to store the answer array. If the output array is not considered, the auxiliary space is O(1).
**Pros:** Simple to understand and implement.
**Cons:** Inefficient and will likely result in a "Time Limit Exceeded" error for large inputs due to the nested loops.
### Explanation
This method directly translates the problem statement into code. For every single query, we perform a linear scan through the entire `items` array. We maintain a variable, `maxBeauty`, initialized to zero. During the scan, if we find an item whose price is less than or equal to the current query's price limit, we compare its beauty with our current `maxBeauty` and update it if the item's beauty is greater. This process is repeated for all queries.

```java
class Solution {
    public int[] maximumBeauty(int[][] items, int[] queries) {
        int[] answer = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int maxBeauty = 0;
            int queryPrice = queries[i];
            for (int[] item : items) {
                int price = item[0];
                int beauty = item[1];
                if (price <= queryPrice) {
                    maxBeauty = Math.max(maxBeauty, beauty);
                }
            }
            answer[i] = maxBeauty;
        }
        return answer;
    }
}
```
### Algorithm
*   Initialize an `answer` array of the same size as `queries`, filled with zeros.
*   Loop through each query `q` with index `i` in the `queries` array.
*   For each query `q`, initialize a variable `maxBeauty` to 0.
*   Loop through every `item` in the `items` array.
*   If the price of the `item` (`item[0]`) is less than or equal to the query `q`, update `maxBeauty` to be the maximum of its current value and the beauty of the item (`item[1]`).
*   After checking all items, store the final `maxBeauty` in `answer[i]`.
*   After iterating through all queries, return the `answer` array.

## Sorting Items with Binary Search (TreeMap)
This approach improves upon the brute-force method by pre-processing the `items` data. We first sort the items by price and then create a data structure that allows for efficient lookups. A `TreeMap` is ideal here as it stores keys (prices) in sorted order and allows for finding the highest price less than or equal to a given query price in logarithmic time.
**Time:** O(N log N + Q log N). Populating the TreeMap takes O(N log K) where K is the number of unique prices (K <= N). Processing the map takes O(K). Each of the Q queries takes O(log K) for `floorEntry`. The total is dominated by O(N log N + Q log N). · **Space:** O(N) to store the TreeMap, which can have up to N unique prices.
**Pros:** Significantly faster than brute force for large inputs.; The use of `TreeMap` simplifies the implementation of binary search logic.
**Cons:** Higher space complexity than the brute-force approach.
### Explanation
The core idea is to pre-calculate the maximum beauty available for any price up to a certain point. A `TreeMap` is used to store a mapping from a price to the maximum beauty of an item available at or below that price. 

First, we populate the `TreeMap` with the maximum beauty for each unique price point from the `items` array. This handles cases where multiple items have the same price. Then, we iterate through the `TreeMap` (which keeps entries sorted by price) and update each entry's value to be the maximum beauty seen so far. This ensures that for any price `p`, `map.get(p)` will represent the maximum beauty among all items with price less than or equal to `p`. 

For each query, we can then use the `TreeMap.floorEntry()` method, which performs a binary search-like operation to find the answer in logarithmic time.

```java
import java.util.TreeMap;
import java.util.Map;

class Solution {
    public int[] maximumBeauty(int[][] items, int[] queries) {
        TreeMap<Integer, Integer> priceToMaxBeautyMap = new TreeMap<>();
        // A value of 0 for a price that doesn't exist.
        priceToMaxBeautyMap.put(0, 0);

        for (int[] item : items) {
            int price = item[0];
            int beauty = item[1];
            priceToMaxBeautyMap.put(price, Math.max(priceToMaxBeautyMap.getOrDefault(price, 0), beauty));
        }
        
        int maxBeautySoFar = 0;
        for (Map.Entry<Integer, Integer> entry : priceToMaxBeautyMap.entrySet()) {
            maxBeautySoFar = Math.max(maxBeautySoFar, entry.getValue());
            entry.setValue(maxBeautySoFar);
        }
        
        int[] answer = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int queryPrice = queries[i];
            Map.Entry<Integer, Integer> entry = priceToMaxBeautyMap.floorEntry(queryPrice);
            answer[i] = entry.getValue();
        }
        
        return answer;
    }
}
```
### Algorithm
*   Create a `TreeMap<Integer, Integer>` called `priceToMaxBeautyMap`. The TreeMap will store prices as keys and the maximum beauty for that price as values.
*   First, process the `items` to find the maximum beauty for each unique price. Iterate through `items` and for each `[price, beauty]`, update the map: `map.put(price, max(current_max_beauty_for_price, beauty))`.
*   After the first pass, the map contains the max beauty for each *exact* price. Now, update it so that `map.get(p)` returns the max beauty for any price `<= p`. Iterate through the map's entries (which are sorted by price) and ensure each value is at least as large as the previous one.
*   Initialize `maxBeautySoFar = 0`. Iterate through the map's entries. For each entry, update its value to `max(maxBeautySoFar, entry.getValue())`, and then update `maxBeautySoFar` with this new value.
*   Initialize an `answer` array.
*   For each `queryPrice` in `queries`, use the `TreeMap.floorEntry(queryPrice)` method. This method efficiently finds the entry with the greatest key less than or equal to `queryPrice`.
*   If `floorEntry` returns a valid entry, its value is the maximum beauty for the query. If it returns `null`, the answer is 0.
*   Store the result in the `answer` array and return it.

## Sorting Items and Queries (Two Pointers)
This is one of the most optimal approaches. It involves sorting both the `items` array (by price) and the `queries` array. By processing the queries in increasing order of price, we can efficiently find the maximum beauty. We use a two-pointer technique, one for items and one for queries, to avoid re-scanning items for each query.
**Time:** O(N log N + Q log Q). Sorting `items` takes O(N log N). Sorting `indexedQueries` takes O(Q log Q). The two-pointer traversal takes O(N + Q) because each item and each query is visited only once. The total complexity is dominated by the sorting steps. · **Space:** O(Q) to store `indexedQueries` and the `answer` array.
**Pros:** Highly efficient in both time and space.; Often faster in practice than the TreeMap approach due to better memory access patterns and lower constant factors.
**Cons:** Slightly more complex to implement due to the need to handle original query indices.
### Explanation
The key insight is that if we process queries in increasing order of price, the set of available items only grows. This allows for a single pass over the `items` array across all queries. 

First, we sort the `items` by price. Then, because we must return answers in the original query order, we pair each query with its original index before sorting the queries by price. We then iterate through the sorted queries. We use one pointer for the sorted queries and another for the sorted items. As we move to a query with a higher price limit, we advance the item pointer to include all new items that are now affordable, updating a `maxBeauty` variable along the way. The `maxBeauty` at each step is the answer for the current query, which we place in our result array at its original index.

```java
import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public int[] maximumBeauty(int[][] items, int[] queries) {
        // Sort items by price
        Arrays.sort(items, Comparator.comparingInt(a -> a[0]));
        
        // Create indexed queries to keep track of original indices
        int[][] indexedQueries = new int[queries.length][2];
        for (int i = 0; i < queries.length; i++) {
            indexedQueries[i][0] = queries[i];
            indexedQueries[i][1] = i;
        }
        
        // Sort queries by price
        Arrays.sort(indexedQueries, Comparator.comparingInt(a -> a[0]));
        
        int[] answer = new int[queries.length];
        int itemIndex = 0;
        int maxBeauty = 0;
        
        // Iterate through sorted queries
        for (int i = 0; i < queries.length; i++) {
            int queryPrice = indexedQueries[i][0];
            int originalIndex = indexedQueries[i][1];
            
            // Move item pointer and update max beauty for items within budget
            while (itemIndex < items.length && items[itemIndex][0] <= queryPrice) {
                maxBeauty = Math.max(maxBeauty, items[itemIndex][1]);
                itemIndex++;
            }
            
            answer[originalIndex] = maxBeauty;
        }
        
        return answer;
    }
}
```
### Algorithm
*   Sort the `items` array based on price in ascending order.
*   Create a 2D array `indexedQueries` where each element is `[query_price, original_index]` to preserve the original order.
*   Sort `indexedQueries` based on `query_price`.
*   Initialize an `answer` array, an `itemPointer` to 0, and `maxBeauty` to 0.
*   Iterate through the sorted `indexedQueries`. For each `[currentQueryPrice, originalIndex]`:
    *   Advance the `itemPointer` through the sorted `items` array as long as the item's price is less than or equal to `currentQueryPrice`.
    *   While advancing, update `maxBeauty` with the beauty of each considered item: `maxBeauty = max(maxBeauty, items[itemPointer][1])`.
    *   After the inner loop, the current `maxBeauty` is the answer for `currentQueryPrice`. Store this value in the `answer` array at the `originalIndex`.
*   Return the `answer` array.

# Solutions
### Java

```java
class Solution {
public
  int[] maximumBeauty(int[][] items, int[] queries) {
    Arrays.sort(items, (a, b)->a[0] - b[0]);
    for (int i = 1; i < items.length; ++i) {
      items[i][1] = Math.max(items[i - 1][1], items[i][1]);
    }
    int n = queries.length;
    int[] ans = new int[n];
    for (int i = 0; i < n; ++i) {
      int left = 0, right = items.length;
      while (left < right) {
        int mid = (left + right) >> 1;
        if (items[mid][0] > queries[i]) {
          right = mid;
        } else {
          left = mid + 1;
        }
      }
      if (left > 0) {
        ans[i] = items[left - 1][1];
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> maximumBeauty(vector<vector<int>> &items, vector<int> &queries) {
    sort(items.begin(), items.end());
    for (int i = 1; i < items.size(); ++i)
      items[i][1] = max(items[i - 1][1], items[i][1]);
    int n = queries.size();
    vector<int> ans(n);
    for (int i = 0; i < n; ++i) {
      int left = 0, right = items.size();
      while (left < right) {
        int mid = (left + right) >> 1;
        if (items[mid][0] > queries[i])
          right = mid;
        else
          left = mid + 1;
      }
      if (left)
        ans[i] = items[left - 1][1];
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]: items . sort() prices = [p for p, _ in items] mx = [items[0][1]] for _, b in items[1:]: mx . append(max(mx[- 1], b)) ans = [0] * len(queries) for i, q in enumerate(queries): j = bisect_right(prices, q) if j: ans[i] = mx[j - 1] return ans

```