2070. Most Beautiful Item for Each Query LeetCode Solution
In this guide, you will get 2070. Most Beautiful Item for Each Query LeetCode Solution with the best time and space complexity. The solution to Most Beautiful Item for Each Query problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Most Beautiful Item for Each Query
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.
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.
2070. Most Beautiful Item for Each Query LeetCode Solution in C++
class Solution {
public:
vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {
vector<int> ans;
vector<int> prices;
vector<int> maxBeautySoFar(items.size() + 1);
ranges::sort(items);
for (const vector<int>& item : items)
prices.push_back(item[0]);
for (int i = 0; i < items.size(); ++i)
maxBeautySoFar[i + 1] = max(maxBeautySoFar[i], items[i][1]);
for (const int query : queries) {
const int i = ranges::upper_bound(prices, query) - prices.begin();
ans.push_back(maxBeautySoFar[i]);
}
return ans;
}
}; /* code provided by PROGIEZ */
2070. Most Beautiful Item for Each Query LeetCode Solution in Java
class Solution {
public int[] maximumBeauty(int[][] items, int[] queries) {
int[] ans = new int[queries.length];
int[] prices = new int[items.length];
int[] maxBeautySoFar = new int[items.length + 1];
Arrays.sort(items, (a, b) -> Integer.compare(a[0], b[0]));
for (int i = 0; i < items.length; ++i)
maxBeautySoFar[i + 1] = Math.max(maxBeautySoFar[i], items[i][1]);
for (int i = 0; i < queries.length; ++i) {
final int index = firstGreater(items, queries[i]);
ans[i] = maxBeautySoFar[index];
}
return ans;
}
private int firstGreater(int[][] items, int q) {
int l = 0;
int r = items.length;
while (l < r) {
final int m = (l + r) / 2;
if (items[m][0] > q)
r = m;
else
l = m + 1;
}
return l;
}
} // code provided by PROGIEZ
2070. Most Beautiful Item for Each Query LeetCode Solution in Python
class Solution:
def maximumBeauty(
self,
items: list[list[int]],
queries: list[int],
) -> list[int]:
prices, beauties = zip(*sorted(items))
maxBeautySoFar = [0] * (len(beauties) + 1)
for i, beauty in enumerate(beauties):
maxBeautySoFar[i + 1] = max(maxBeautySoFar[i], beauty)
return [maxBeautySoFar[bisect_right(prices, query)] for query in queries] # code by PROGIEZ
