Problem Statement
Brute Force [TLE]
class Solution:
def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:
res = [0] * len(queries)
heapq.heapify(items)
for i, q in enumerate(queries):
min_heap = items[:]
ans = float('-inf')
while min_heap:
price, beauty = heapq.heappop(min_heap)
if price <= q:
ans = max(ans, beauty)
else:
break
res[i] = (ans if ans != float('-inf') else 0)
return res
class Solution:
def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:
res = [0] * len(queries)
items.sort(key=lambda x: [x[0], -x[1]])
for i, query in enumerate(queries):
ans = float('-inf')
for price, beauty in items:
if price <= query:
ans = max(ans, beauty)
else:
break
res[i] = (ans if ans != float('-inf') else 0)
return res
Editorial
Approach 1: Sorting Items + Binary Search
class Solution:
def maximumBeauty(
self, items: List[List[int]], queries: List[int]
) -> List[int]:
# Sort and store max beauty
items.sort(key=lambda x: x[0])
max_beauty = items[0][1]
for i in range(len(items)):
max_beauty = max(max_beauty, items[i][1])
items[i][1] = max_beauty
return [self.binary_search(items, q) for q in queries]
def binary_search(self, items, target_price):
left, right = 0, len(items) - 1
max_beauty = 0
while left <= right:
mid = (left + right) // 2
if items[mid][0] > target_price:
right = mid - 1
else:
# Found viable price. Keep moving to right
max_beauty = max(max_beauty, items[mid][1])
left = mid + 1
return max_beauty
Approach 2: Sorting Items + Sorting Queries
class Solution:
def maximumBeauty(self, items, queries):
ans = [0] * len(queries)
# sort both items and queries in ascending order
items.sort(key=lambda x: x[0])
queries_with_indices = [[queries[i], i] for i in range(len(queries))]
queries_with_indices.sort(key=lambda x: x[0])
item_index = 0
max_beauty = 0
for i in range(len(queries)):
query = queries_with_indices[i][0]
original_index = queries_with_indices[i][1]
while item_index < len(items) and items[item_index][0] <= query:
max_beauty = max(max_beauty, items[item_index][1])
item_index += 1
ans[original_index] = max_beauty
return ans
