Sponsored
Sponsored
In this approach, we perform the following steps:
Time Complexity: O((n + m) log n) where n = number of items and m = number of queries.
Space Complexity: O(n) for storing the processed items data.
1def maxBeautyForQueries(items, queries):
2 items = sorted(items)
3 max_beauty = [0] * len(items)
4 current_max = 0
5
6 for i, (price, beauty) in enumerate(items):
7 current_max = max(current_max, beauty)
8 max_beauty[i] = current_max
9
10 def findBest(query):
11 left, right = 0, len(items) - 1
12 while left <= right:
13 mid = (left + right) // 2
14 if items[mid][0] <= query:
15 left = mid + 1
16 else:
17 right = mid - 1
18 return max_beauty[right] if right >= 0 else 0
19
20 return [findBest(q) for q in queries]
21
22# Example usage
23items = [[1,2],[3,2],[2,4],[5,6],[3,5]]
24queries = [1,2,3,4,5,6]
25print(maxBeautyForQueries(items, queries))Python handles the sorted list of items by computing a cumulative record of the best beauty seen by iterating. Then, it directly applies binary search per query, making it extremely fast especially with large datasets.
Coordinate compression can be used to reduce problem complexity when dealing with large range values like prices. In this approach:
Time Complexity: O((n + m) log(n + m)) due to sorting during compression.
Space Complexity: O(n + m) for storing all price points and decision arrays.
This solution first compresses the range of prices into indexes, reducing the search space. A dynamic programming approach then determines the maximum beauty at each possible price point index, allowing quick lookup when answering queries. This methodology deals efficiently with large query ranges.