Most Beautiful Item for Each Query

Problem Description

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.

Key Insights

• Each item has a price and a beauty value, and we need to quickly retrieve the maximum beauty for given price constraints.
• Sorting the items by price allows for efficient querying using binary search.
• By maintaining a running maximum of beauty values as we traverse the sorted items, we can answer each query in logarithmic time.

Space and Time Complexity

Time Complexity: O(N log N + Q log N), where N is the number of items and Q is the number of queries. Space Complexity: O(N), for storing the sorted items and the maximum beauty values.

Solution

The solution involves the following steps:

1. Sorting the Items: First, sort the items based on the price. This allows us to efficiently check which items can be considered for each query.
2. Building a Max Beauty Array: As we traverse the sorted items, maintain a max_beauty list where each entry at index i represents the maximum beauty of items up to and including the item at index i.
3. Answering Queries: For each query, use binary search to find the largest index in the sorted items where the price is less than or equal to the query price, and retrieve the corresponding maximum beauty.

Code Solutions