⚡Flashcard Drill➔
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

  1. Sort the items by price. Then build a prefix maximum of beauty, so that best[i] is the maximum beauty among the first i + 1 items.
  2. For each query, binary search for the last item whose price is at most the query.
  3. The answer is the prefix maximum at that index, or 0 if no item qualifies.
  4. 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 is bisect_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.
🎯 Drill This Card Now➔

🧩 Related Binary Search Problems