Most Beautiful Item for Each Query
Medium
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.
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]
Example 2:
Input: items = [[1,2],[1,2],[1,3],[1,4]], queries = [1]
Output: [4]
Example 3:
Input: items = [[10,1000]], queries = [5]
Output: [0]
Constraints:
1 <= items.length, queries.length <= 10^5items[i].length == 21 <= pricei, beautyi, queriesj <= 10^9
Given the above constraints, can you implement a solution to efficiently determine the maximum beauty for each query? Explain the time and space complexity of your solution. Also, consider edge cases and how your solution handles them.
Solution
Naive Solution
The brute force approach is to iterate through each query and, for each query, iterate through all items to find the items whose price is less than or equal to the query price. Then, find the maximum beauty among those items.
Code:
def maximum_beauty_naive(items, queries):
answer = []
for query in queries:
max_beauty = 0
for price, beauty in items:
if price <= query:
max_beauty = max(max_beauty, beauty)
answer.append(max_beauty)
return answer
Time Complexity
O(m*n), where n is the number of items and m is the number of queries.
Space Complexity
O(1), excluding the space for the output array.
Optimal Solution
To optimize, we can first sort the items by price. Then, for each item, we can maintain a running maximum of the beauty so that we know the maximum beauty for all items with prices up to a certain point. After that, we can perform a binary search for each query to find the rightmost item whose price is less than or equal to the query price. The beauty of that item will be the maximum beauty for that query.
Algorithm:
- Sort the
itemsarray by price in ascending order. - Create a
max_beautiesarray wheremax_beauties[i]stores the maximum beauty amongitems[0],items[1], ...,items[i]. - For each query:
- Use binary search to find the index of the rightmost item whose price is less than or equal to the query.
- If such an item is found, the answer is
max_beauties[index]. Otherwise, the answer is 0.
Code:
def maximum_beauty_optimal(items, queries):
items.sort()
max_beauties = []
current_max_beauty = 0
for price, beauty in items:
current_max_beauty = max(current_max_beauty, beauty)
max_beauties.append(current_max_beauty)
prices = [price for price, _ in items]
answer = []
for query in queries:
left, right = 0, len(items) - 1
index = -1
while left <= right:
mid = (left + right) // 2
if prices[mid] <= query:
index = mid
left = mid + 1
else:
right = mid - 1
if index == -1:
answer.append(0)
else:
answer.append(max_beauties[index])
return answer
Time Complexity
O(n log n + m log n), where n is the number of items (for sorting) and m is the number of queries (each query requires a binary search with O(log n)).
Space Complexity
O(n) for the max_beauties array.
Edge Cases
- If the items array is empty, all queries should return 0.
- If a query is smaller than the smallest price, the query should return 0.
- If a query is larger than the largest price, it should return the max beauty of all items.
- Duplicate prices and beauties should be handled correctly.
