You are given a 2D integer array items where items[i] = [pricei, beautyi] denotes the price and beauty of an item respectively.
You are also given a 0-indexed integer array queries. For each queries[j], you want to determine the maximum beauty of an item whose price is less than or equal to queries[j]. If no such item exists, then the answer to this query is 0.
Return an array answer of the same length as queries where answer[j] is the answer to the jth query.
Example 1:
Input: items = [[1,2],[3,2],[2,4],[5,6],[3,5]], queries = [1,2,3,4,5,6] Output: [2,4,5,5,6,6] Explanation: - For queries[0]=1, [1,2] is the only item which has price <= 1. Hence, the answer for this query is 2. - For queries[1]=2, the items which can be considered are [1,2] and [2,4]. The maximum beauty among them is 4. - For queries[2]=3 and queries[3]=4, the items which can be considered are [1,2], [3,2], [2,4], and [3,5]. The maximum beauty among them is 5. - For queries[4]=5 and queries[5]=6, all items can be considered. Hence, the answer for them is the maximum beauty of all items, i.e., 6.
Example 2:
Input: items = [[1,2],[1,2],[1,3],[1,4]], queries = [1] Output: [4] Explanation: The price of every item is equal to 1, so we choose the item with the maximum beauty 4. Note that multiple items can have the same price and/or beauty.
Example 3:
Input: items = [[10,1000]], queries = [5] Output: [0] Explanation: No item has a price less than or equal to 5, so no item can be chosen. Hence, the answer to the query is 0.
Constraints:
1 <= items.length, queries.length <= 105items[i].length == 21 <= pricei, beautyi, queries[j] <= 109Problem Overview: You are given items where each item has a price and beauty, and a list of queries representing the maximum price you can pay. For each query, return the maximum beauty among all items with price ≤ query. The challenge is answering many queries efficiently without scanning the entire list every time.
Approach 1: Sort and Binary Search Approach (O((n + q) log n) time, O(n) space)
Sort the items by price. After sorting, build a prefix array where each position stores the maximum beauty seen so far up to that price. This transforms the problem into a monotonic lookup: if you know the largest index whose price is ≤ query, the prefix value already contains the best beauty available.
For every query, run a binary search on the sorted price list to find the rightmost item whose price does not exceed the query value. Return the prefix maximum beauty at that index. Sorting costs O(n log n), and each query takes O(log n), making the full solution O((n + q) log n). The additional space is O(n) for storing prefix maximum values.
This method relies heavily on sorting and binary search. Once the prefix maximum array is built, each query becomes a simple lookup after the search.
Approach 2: Coordinate Compression and Dynamic Programming (O((n + q) log n) time, O(n) space)
Prices can be large and sparse. Coordinate compression maps all unique prices from items and queries into a compact index range. After compression, create a DP array where dp[i] represents the maximum beauty achievable for any price index ≤ i.
First record the maximum beauty for each compressed price from the item list. Then build the DP array using a prefix maximum scan so that every index inherits the best beauty seen so far. For each query, convert its price to the corresponding compressed index (using binary search on the compressed list) and read the DP value directly.
This approach also runs in O((n + q) log n) due to sorting during compression and binary search for query mapping, while the DP prefix pass is linear. Space usage remains O(n). It works well when you want explicit control over price indexing or when integrating with other array-based dynamic programming structures.
Recommended for interviews: The sort + binary search solution is what interviewers typically expect. It demonstrates understanding of preprocessing with prefix maximums and efficient query handling using binary search. The coordinate compression variant shows deeper algorithmic thinking but is rarely required unless the constraints demand more structured indexing.
In this approach, we perform the following steps:
The algorithm first sorts the items based on their price. While traversing through the sorted list, it maintains the maximum beauty for each price. For each query, a binary search is executed on this list of prices to fetch the corresponding maximum beauty. This method ensures optimal handling of both items and queries given constraints.
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.
Coordinate compression can be used to reduce problem complexity when dealing with large range values like prices. In this approach:
This solution first compresses the range of prices into indexes, reducing the search space. A dynamic programming approach then determines the maximum beauty at each possible price point index, allowing quick lookup when answering queries. This methodology deals efficiently with large query ranges.
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.
For each query, we need to find the maximum beauty value among the items with a price less than or equal to the query price. We can use the offline query method, first sort the items by price, and then sort the queries by price.
Next, we traverse the queries from small to large. For each query, we use a pointer i to point to the item array. If the price of the item is less than or equal to the query price, we update the current maximum beauty value and move the pointer i to the right until the price of the item is greater than the query price. We record the current maximum beauty value, which is the answer to the current query. Continue to traverse the next query until all queries are processed.
The time complexity is O(n times log n + m times log m), and the space complexity is O(log n + m). Where n and m are the lengths of the item array and the query array, respectively.
Python
Java
C++
Go
TypeScript
We can sort the items by price, and then preprocess the maximum beauty value of the items that are less than or equal to each price, recorded in the array mx or the original items array.
For each query, we can use binary search to find the index j of the first item with a price greater than the query price, then j - 1 is the index of the item with the maximum beauty value and a price less than or equal to the query price, which is added to the answer.
The time complexity is O((m + n) times log n), and the space complexity is O(n). Where n and m are the lengths of the item array and the query array, respectively.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Sort and Binary Search Approach | Time Complexity: O((n + m) log n) where n = number of items and m = number of queries. |
| Coordinate Compression and Dynamic Programming | Time Complexity: O((n + m) log(n + m)) due to sorting during compression. |
| Sorting + Offline Query | — |
| Sorting + Binary Search | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sort + Prefix Max + Binary Search | O((n + q) log n) | O(n) | Best general solution when handling many queries on price limits |
| Coordinate Compression + Dynamic Programming | O((n + q) log n) | O(n) | Useful when prices are large or sparse and you want compact indexed DP |
Most Beautiful Item for Each Query | Simple Explanation | Leetcode 2070 | codestorywithMIK • codestorywithMIK • 9,050 views views
Watch 9 more video solutions →Practice Most Beautiful Item for Each Query with our built-in code editor and test cases.
Practice on FleetCode