# 2070. Most Beautiful Item for Each Query

• Time: $O(\texttt{sort} + q\log n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution { public: vector maximumBeauty(vector>& items, vector& queries) { vector ans; vector prices; vector maxBeautySoFar(items.size() + 1); sort(items.begin(), items.end()); for (const vector& 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 = upper_bound(prices.begin(), prices.end(), query) - prices.begin(); ans.push_back(maxBeautySoFar[i]); } return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 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) -> 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; } } 
 1 2 3 4 5 6 7 8 9 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]