2070. Most Beautiful Item for Each Query - Detailed Explanation

Problem Statement

Description:
You are given a 2D integer array items where each element items[i] = [price_i, beauty_i] represents an item with a certain price and its beauty value. You are also given an integer array queries, where each queries[j] is a price query. For each query, you must determine the maximum beauty of any item whose price is less than or equal to that query. If no such item exists, return 0 for that query.

Constraints:

• (1 \leq \text{items.length}, \text{queries.length} \leq 10^5)
• (1 \leq price_i, beauty_i, queries[j] \leq 10^9)
• The items array is not necessarily sorted.

Example 1:

• Input:
  items = [[1,2],[3,2],[2,4],[5,6]]
queries = [1,2,3,4,5]
• Output: [2,4,4,4,6]
• Explanation:
  • For query = 1: Items with price ≤ 1 are ([[1,2]]) → maximum beauty = 2.
  • For query = 2: Items with price ≤ 2 are ([[1,2], [2,4]]) → maximum beauty = 4.
  • For query = 3: Items with price ≤ 3 are ([[1,2], [2,4], [3,2]]) → maximum beauty = 4.
  • For query = 4: No new item added beyond price 3, so the answer remains 4.
  • For query = 5: Items with price ≤ 5 are ([[1,2], [2,4], [3,2], [5,6]]) → maximum beauty = 6.

Example 2:

• Input:
  items = [[1,2],[1,3],[2,4]]
queries = [1,2]
• Output: [3,4]
• Explanation:
  • For query = 1: Items with price ≤ 1 are ([[1,2],[1,3]]) → maximum beauty = max(2, 3) = 3.
  • For query = 2: Items with price ≤ 2 are ([[1,2],[1,3],[2,4]]) → maximum beauty = 4.

Hints

• Hint 1: Sorting the items array by price helps quickly identify all items within a given query’s price limit.
• Hint 2: Precompute a running (prefix) maximum of beauty values as you iterate through the sorted items.
• Hint 3: Process the queries in sorted order (while keeping track of their original indices) so you can use a two-pointer technique or binary search to efficiently answer each query.

Approaches

Approach 1: Brute Force

• Idea:
  For each query, iterate over every item and check whether its price is within the query limit. Track the maximum beauty.
• How It Works:
  • For each query (q), loop over all items.
  • If an item’s price ≤ (q), update the current maximum beauty.
• Drawback & Complexity:
  • Time Complexity: (O(q \times n)), which is too slow when both arrays have up to (10^5) elements.
  • Space Complexity: (O(1)) (ignoring output storage).

Approach 2: Two-Pointer Technique (Sorting Queries and Items)

• Idea:
  Sort the items array by price. Also, sort the queries along with their original indices. Then, use a two-pointer technique to traverse the sorted items and update a running maximum beauty.
• How It Works:
  1. Sort Items:
     Sort items in ascending order by price.
  2. Sort Queries:
     Pair each query with its original index and sort these pairs by the query value.
  3. Two-Pointer Scan:
     Initialize a pointer for items and a variable maxBeauty to 0. For each query (in sorted order), advance the pointer while the item price is ≤ the query value. Update maxBeauty with the highest beauty encountered so far. Assign maxBeauty to the result corresponding to the query’s original index.
• Complexity:
  • Time Complexity: (O(n \log n + q \log q + n + q)).
  • Space Complexity: (O(n + q)).

Approach 3: Binary Search with Prefix Maximum

• Idea:
  Sort the items array by price and build a prefix array where each element is the maximum beauty up to that price. Then, for each query, use binary search to quickly find the appropriate prefix maximum.
• How It Works:

  1. Sort Items:
     Sort by price.

  2. Build Prefix Maximum Array:
     Create an array prefixBeauty where prefixBeauty[i] is the maximum beauty among items from index 0 to (i).

  3. Answer Queries with Binary Search:
     For each query, perform a binary search on the sorted items array to find the largest index with price ≤ query, then return the corresponding value from prefixBeauty.

• Complexity:
  • Time Complexity: (O(n \log n + q \log n)).
  • Space Complexity: (O(n + q)).

Python Code

Below is the Python implementation using the two-pointer technique: