#2070

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Most Beautiful Item for Each Query

Determine the maximum beauty of items affordable for each query using efficient binary search and sorting techniques.

Problem Statement

You are given a list of items, each with a price and beauty score. For every query representing a budget, you need to find the maximum beauty among items whose price does not exceed that budget.

Return an array where each element corresponds to a query and contains the highest achievable beauty. If no items are affordable for a query, return 0 for that 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]

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]

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]

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 <= 105
items[i].length == 2
1 <= pricei, beautyi, queries[j] <= 109

Solution Approach

Sort Items by Price and Track Maximum Beauty

Sort the items based on price and maintain a running maximum beauty. This ensures that as you iterate through items, you always know the best beauty up to the current price, which is crucial for efficient query processing.

Sort Queries and Map Results

Sort queries along with their original indices. This allows processing in increasing order of budget, aligning with the sorted items, so that each query can incrementally update the maximum beauty without redundant checks.

Binary Search Over Valid Items

For each query, use a pointer or binary search over the sorted items to determine the highest beauty within the budget. This pattern avoids O(N*M) scanning and leverages the sorted order to efficiently answer each query.

Complexity Analysis

Metric	Value
Time	O(M \cdot \log M + N \cdot \log N)
Space	O(S_M + S_N + N)

Sorting items and queries takes O(M log M + N log N). Iterating through items for all queries adds O(N + M). Total space is O(N + M) to store sorted structures and results.

What Interviewers Usually Probe

Ask about optimizing query processing to avoid scanning all items for each query.
Probe understanding of binary search applied over an answer space rather than indices.
Check if candidate recognizes the need to maintain running maximum beauty while iterating.

Common Pitfalls or Variants

Common pitfalls

Ignoring multiple items with the same price and not picking the maximum beauty among them.
Processing queries in arbitrary order, causing repeated item scans and higher complexity.
Forgetting to handle queries with no affordable items, resulting in incorrect zeros.

Follow-up variants

Items may have duplicate prices but different beauties; consider keeping only the maximum beauty per price.
Queries could be very large numbers; ensure binary search or pointer logic efficiently handles these ranges.
Instead of a single maximum beauty, return the top K beauties for each query, requiring modified data structures.

FAQ

What is the key strategy for Most Beautiful Item for Each Query?

Sort items by price, maintain a running maximum beauty, and process queries in sorted order to efficiently answer using a binary search approach.

Can multiple items with the same price affect the answer?

Yes, always consider the item with the maximum beauty among duplicates to ensure correct query results.

How do I handle queries that have no affordable items?

Return 0 for any query whose budget is less than the lowest priced item.

What is the time complexity for this pattern?

Sorting items and queries is O(M log M + N log N) and answering queries incrementally is O(M + N), yielding overall efficient performance.

Why is this considered binary search over the answer space?

Instead of searching indices directly, we check which items satisfy the budget constraints, effectively performing a search over valid item prices for each query.

terminal

Solution

Solution 1: Sorting + Offline Query

For each query, we need to find the maximum beauty value among the items with a price less than or equal to the query price. We can use the offline query method, first sort the items by price, and then sort the queries by price.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:
        items.sort()
        n, m = len(items), len(queries)
        ans = [0] * len(queries)
        i = mx = 0
        for q, j in sorted(zip(queries, range(m))):
            while i < n and items[i][0] <= q:
                mx = max(mx, items[i][1])
                i += 1
            ans[j] = mx
        return ans

Solution 2: Sorting + Binary Search

We can sort the items by price, and then preprocess the maximum beauty value of the items that are less than or equal to each price, recorded in the array $mx$ or the original $items$ array.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:
        items.sort()
        n, m = len(items), len(queries)
        ans = [0] * len(queries)
        i = mx = 0
        for q, j in sorted(zip(queries, range(m))):
            while i < n and items[i][0] <= q:
                mx = max(mx, items[i][1])
                i += 1
            ans[j] = mx
        return ans

Continue Practicing

#2071 maximum number of tasks you can assign #2054 two best non overlapping events #2089 find target indices after sorting array