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.
JavaScript code makes full use of Sets and Maps for efficient price compression, mapping these prices to maintained beauty maximums for fast index-based query responses. This enables quick filter and calculate actions post-compression.