NeetCode #290LC-2070MediumBinary Search
← Back to All Problems#290 · #2070 · Most Beautiful Item for Each Query(每一个查询的最大美丽值)
📌 Problem Statement & Constraints
You are given a 2D array
items where items[i] = [price_i, beauty_i], and an array of queries. For each query, return the maximum beauty among all items with price at most that query. If no such item exists, return 0. Constraints: 1 <= items.length, queries.length <= 10^5, 1 <= price, beauty, query <= 10^9.💡 Core Algorithmic Approaches
- Sort the items by price. Then build a prefix maximum of beauty, so that
best[i]is the maximum beauty among the firsti + 1items. - For each query, binary search for the last item whose price is at most the query.
- The answer is the prefix maximum at that index, or 0 if no item qualifies.
- This gives O((n + q) log n), far better than a per-query linear scan.
💻 Benchmark Python3 Implementation
class Solution:
def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:
from bisect import bisect_right
items.sort() # by price, then beauty
prices = []
best = []
cur = 0
for p, b in items:
cur = max(cur, b)
prices.append(p)
best.append(cur) # prefix maximum of beauty
res = []
for q in queries:
i = bisect_right(prices, q) - 1 # last item with price <= q
res.append(best[i] if i >= 0 else 0)
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O((n + q) log n): sorting plus a binary search per query.
💾 Space Complexity
O(n) for the prefix maxima.
⚠️ Interview Pitfalls & Follow-ups
- Scanning all items per query: O(n * q) = 10^10 operations, which times out.
- Storing the maximum beauty without the prefix structure: the query may admit several items, so the prefix maximum is required.
- Using
bisect_left: you want the last price at most the query, which isbisect_right(...) - 1. - Returning the beauty of the closest item rather than the maximum: the prefix maximum is the key.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.