Welcome to Subscribe On Youtube
2070. Most Beautiful Item for Each Query
Description
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 <= 105items[i].length == 21 <= pricei, beautyi, queries[j] <= 109
Solutions
-
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; } } -
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; } }; -
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 -
func maximumBeauty(items [][]int, queries []int) []int { sort.Slice(items, func(i, j int) bool { return items[i][0] < items[j][0] }) for i := 1; i < len(items); i++ { items[i][1] = max(items[i-1][1], items[i][1]) } n := len(queries) ans := make([]int, n) for i, v := range queries { left, right := 0, len(items) for left < right { mid := (left + right) >> 1 if items[mid][0] > v { right = mid } else { left = mid + 1 } } if left > 0 { ans[i] = items[left-1][1] } } return ans } -
function maximumBeauty(items: number[][], queries: number[]): number[] { const n = items.length; const m = queries.length; items.sort((a, b) => a[0] - b[0]); const idx: number[] = Array(m) .fill(0) .map((_, i) => i); idx.sort((i, j) => queries[i] - queries[j]); let [i, mx] = [0, 0]; const ans: number[] = Array(m).fill(0); for (const j of idx) { while (i < n && items[i][0] <= queries[j]) { mx = Math.max(mx, items[i][1]); ++i; } ans[j] = mx; } return ans; }