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.

Examples

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.

Similar Problems

Maximum Profit in Job Scheduling Problem Maximum Earnings From Taxi Problem Maximum Number of Events That Can Be Attended Problem Two Best Non-Overlapping Events Problem

Solution

Method 1 - Sorting + Binary Search

To solve the problem, we need to efficiently determine the maximum beauty of an item whose price is less than or equal to each query price.

Here is the approach:

  1. Sort the Items:
    • First, sort the items array based on the item prices in ascending order.
    • Track the maximum beauty encountered so far as we sort to ensure that each item price is associated with the maximum beauty up to that price.
  2. Process the Queries:
    • Sort the queries keeping track of their original indices to efficiently place results back in their original order.
    • Use a pointer to traverse through the sorted items and find the maximum beauty for each query price.
    • If an item’s price is less than or equal to the query price, update the maximum beauty.
  3. Binary Search:
    • For each query, use binary search (or two-pointer technique) to find the relevant items efficiently ensuring that the solution is optimized.

Code

Java
class Solution {
    public int[] maximumBeauty(int[][] items, int[] queries) {
        Arrays.sort(items, Comparator.comparingInt(a -> a[0]));
        int[] maxBeauty = new int[items.length];
        maxBeauty[0] = items[0][1];
        for (int i = 1; i < items.length; i++) {
            maxBeauty[i] = Math.max(maxBeauty[i - 1], items[i][1]);
        }

        int[][] qWithIndex = new int[queries.length][2];
        for (int i = 0; i < queries.length; i++) {
            qWithIndex[i][0] = queries[i];
            qWithIndex[i][1] = i;
        }
        Arrays.sort(qWithIndex, Comparator.comparingInt(a -> a[0]));

        int[] ans = new int[queries.length];
        int idx = 0;
        for (int[] q : qWithIndex) {
            while (idx < items.length && items[idx][0] <= q[0]) {
                idx++;
            }
            ans[q[1]] = idx == 0 ? 0 : maxBeauty[idx - 1];
        }
        return ans;
    }
}
Python
class Solution:
    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:
        items.sort()
        max_beauties = [0] * len(items)
        max_beauties[0] = items[0][1]
        for i in range(1, len(items)):
            max_beauties[i] = max(max_beauties[i - 1], items[i][1])
        
        sorted_queries = sorted((q, i) for i, q in enumerate(queries))
        
        ans = [0] * len(queries)
        idx = 0
        for price, q_idx in sorted_queries:
            while idx < len(items) and items[idx][0] <= price:
                idx += 1
            ans[q_idx] = max_beauties[idx - 1] if idx > 0 else 0
        
        return ans

Complexity

  • ⏰ Time complexity: O((n + m) log n)
    • Sorting the items array: O(n log n)
    • Sorting the queries array: O(m log m)
    • Processing each query using a pointer: O(n + m)
    • Overall: O((n + m) log n)
  • 🧺 Space complexity: O(n + m)

Method 2 -

Code

Java
Python

Complexity

  • ⏰ Time complexity: O(NNNXXXNNN)
  • 🧺 Space complexity: O(NNNXXX)