Formatted question description: https://leetcode.ca/all/2070.html

2070. Most Beautiful Item for Each Query (Medium)

You are given a 2D integer array items where items[i] = [price_i, beauty_i] 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 j^th 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 <= 10⁵
items[i].length == 2
1 <= price_i, beauty_i, queries[j] <= 10⁹

Similar Questions:

Closest Room (Hard)

Solution 1. Offline Query

Sort both items and queries in ascending order of price. Traverse queries. Use a pointer i to cover all the items with a price <= the current query, and compute the maximum beauty among them. In this way, we traverse both array only once.

// OJ: https://leetcode.com/problems/most-beautiful-item-for-each-query/
// Time: O(NlogN + MlogM + M + N) where `N`/`M` is the length of `items`/`queries`.
// Space: O(M)
class Solution {
public:
    vector<int> maximumBeauty(vector<vector<int>>& A, vector<int>& Q) {
        vector<pair<int, int>> queries;
        for (int i = 0; i < Q.size(); ++i) queries.push_back({Q[i],i});
        sort(begin(queries), end(queries));
        sort(begin(A), end(A));
        int i = 0, N = A.size(), maxBeauty = 0;
        vector<int> ans(Q.size());
        for (auto q : queries) {
            auto &[query, index] = q;
            for (; i < N && A[i][0] <= query; ++i) maxBeauty = max(maxBeauty, A[i][1]);
            ans[index] = maxBeauty;
        }
        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

############

# 2070. Most Beautiful Item for Each Query
# https://leetcode.com/problems/most-beautiful-item-for-each-query/

class Solution:
    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:
        n = len(items)
        items.sort(key = lambda x : (x[0], -x[1]))
        res = []
        A = [(0, 0)]
        curr = 0

        for i, (price, beauty) in enumerate(items):
            if i > 1 and price == items[i - 1][0]: continue
                
            curr = max(curr, beauty)
            A.append((price, curr))

        for q in queries:
            index = bisect.bisect(A, (q + 1, )) - 1
            res.append(A[index][1])
            
        return res
            

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;
    }
}

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
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

Discuss

https://leetcode.com/problems/most-beautiful-item-for-each-query/discuss/1576065/C%2B%2B-Offline-Query

2070 - Most Beautiful Item for Each Query

2070. Most Beautiful Item for Each Query (Medium)

Solution 1. Offline Query

Discuss

All Problems

All Solutions

Welcome to Subscribe On Youtube

2070. Most Beautiful Item for Each Query (Medium)

Solution 1. Offline Query

Discuss

All Problems

All Solutions