Most Beautiful Item for Each Query
MedPrompt
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] <= 109
Approaches
3 approaches with complexity analysis and trade-offs.
A simple and straightforward approach. For each query, we iterate through all the items. If an item's price is within the query's budget, we consider its beauty. We keep track of the maximum beauty found for each query.
Algorithm
- Initialize an
answerarray of the same size asqueries, filled with zeros. - Loop through each query
qwith indexiin thequeriesarray. - For each query
q, initialize a variablemaxBeautyto 0. - Loop through every
itemin theitemsarray. - If the price of the
item(item[0]) is less than or equal to the queryq, updatemaxBeautyto be the maximum of its current value and the beauty of the item (item[1]). - After checking all items, store the final
maxBeautyinanswer[i]. - After iterating through all queries, return the
answerarray.
Walkthrough
This method directly translates the problem statement into code. For every single query, we perform a linear scan through the entire items array. We maintain a variable, maxBeauty, initialized to zero. During the scan, if we find an item whose price is less than or equal to the current query's price limit, we compare its beauty with our current maxBeauty and update it if the item's beauty is greater. This process is repeated for all queries.
class Solution { public int[] maximumBeauty(int[][] items, int[] queries) { int[] answer = new int[queries.length]; for (int i = 0; i < queries.length; i++) { int maxBeauty = 0; int queryPrice = queries[i]; for (int[] item : items) { int price = item[0]; int beauty = item[1]; if (price <= queryPrice) { maxBeauty = Math.max(maxBeauty, beauty); } } answer[i] = maxBeauty; } return answer; }}Complexity
Time
O(N * Q), where N is the number of items and Q is the number of queries. For each of the Q queries, we perform a linear scan of N items.
Space
O(Q) to store the answer array. If the output array is not considered, the auxiliary space is O(1).
Trade-offs
Pros
Simple to understand and implement.
Cons
Inefficient and will likely result in a "Time Limit Exceeded" error for large inputs due to the nested loops.
This approach improves upon the brute-force method by pre-processing the items data. We first sort the items by price and then create a data structure that allows for efficient lookups. A TreeMap is ideal here as it stores keys (prices) in sorted order and allows for finding the highest price less than or equal to a given query price in logarithmic time.
Algorithm
- Create a
TreeMap<Integer, Integer>calledpriceToMaxBeautyMap. The TreeMap will store prices as keys and the maximum beauty for that price as values. - First, process the
itemsto find the maximum beauty for each unique price. Iterate throughitemsand for each[price, beauty], update the map:map.put(price, max(current_max_beauty_for_price, beauty)). - After the first pass, the map contains the max beauty for each exact price. Now, update it so that
map.get(p)returns the max beauty for any price<= p. Iterate through the map's entries (which are sorted by price) and ensure each value is at least as large as the previous one. - Initialize
maxBeautySoFar = 0. Iterate through the map's entries. For each entry, update its value tomax(maxBeautySoFar, entry.getValue()), and then updatemaxBeautySoFarwith this new value. - Initialize an
answerarray. - For each
queryPriceinqueries, use theTreeMap.floorEntry(queryPrice)method. This method efficiently finds the entry with the greatest key less than or equal toqueryPrice. - If
floorEntryreturns a valid entry, its value is the maximum beauty for the query. If it returnsnull, the answer is 0. - Store the result in the
answerarray and return it.
Walkthrough
The core idea is to pre-calculate the maximum beauty available for any price up to a certain point. A TreeMap is used to store a mapping from a price to the maximum beauty of an item available at or below that price.
First, we populate the TreeMap with the maximum beauty for each unique price point from the items array. This handles cases where multiple items have the same price. Then, we iterate through the TreeMap (which keeps entries sorted by price) and update each entry's value to be the maximum beauty seen so far. This ensures that for any price p, map.get(p) will represent the maximum beauty among all items with price less than or equal to p.
For each query, we can then use the TreeMap.floorEntry() method, which performs a binary search-like operation to find the answer in logarithmic time.
import java.util.TreeMap;import java.util.Map; class Solution { public int[] maximumBeauty(int[][] items, int[] queries) { TreeMap<Integer, Integer> priceToMaxBeautyMap = new TreeMap<>(); // A value of 0 for a price that doesn't exist. priceToMaxBeautyMap.put(0, 0); for (int[] item : items) { int price = item[0]; int beauty = item[1]; priceToMaxBeautyMap.put(price, Math.max(priceToMaxBeautyMap.getOrDefault(price, 0), beauty)); } int maxBeautySoFar = 0; for (Map.Entry<Integer, Integer> entry : priceToMaxBeautyMap.entrySet()) { maxBeautySoFar = Math.max(maxBeautySoFar, entry.getValue()); entry.setValue(maxBeautySoFar); } int[] answer = new int[queries.length]; for (int i = 0; i < queries.length; i++) { int queryPrice = queries[i]; Map.Entry<Integer, Integer> entry = priceToMaxBeautyMap.floorEntry(queryPrice); answer[i] = entry.getValue(); } return answer; }}Complexity
Time
O(N log N + Q log N). Populating the TreeMap takes O(N log K) where K is the number of unique prices (K <= N). Processing the map takes O(K). Each of the Q queries takes O(log K) for `floorEntry`. The total is dominated by O(N log N + Q log N).
Space
O(N) to store the TreeMap, which can have up to N unique prices.
Trade-offs
Pros
Significantly faster than brute force for large inputs.
The use of
TreeMapsimplifies the implementation of binary search logic.
Cons
Higher space complexity than the brute-force approach.
This is one of the most optimal approaches. It involves sorting both the items array (by price) and the queries array. By processing the queries in increasing order of price, we can efficiently find the maximum beauty. We use a two-pointer technique, one for items and one for queries, to avoid re-scanning items for each query.
Algorithm
- Sort the
itemsarray based on price in ascending order. - Create a 2D array
indexedQuerieswhere each element is[query_price, original_index]to preserve the original order. - Sort
indexedQueriesbased onquery_price. - Initialize an
answerarray, anitemPointerto 0, andmaxBeautyto 0. - Iterate through the sorted
indexedQueries. For each[currentQueryPrice, originalIndex]:- Advance the
itemPointerthrough the sorteditemsarray as long as the item's price is less than or equal tocurrentQueryPrice. - While advancing, update
maxBeautywith the beauty of each considered item:maxBeauty = max(maxBeauty, items[itemPointer][1]). - After the inner loop, the current
maxBeautyis the answer forcurrentQueryPrice. Store this value in theanswerarray at theoriginalIndex.
- Advance the
- Return the
answerarray.
Walkthrough
The key insight is that if we process queries in increasing order of price, the set of available items only grows. This allows for a single pass over the items array across all queries.
First, we sort the items by price. Then, because we must return answers in the original query order, we pair each query with its original index before sorting the queries by price. We then iterate through the sorted queries. We use one pointer for the sorted queries and another for the sorted items. As we move to a query with a higher price limit, we advance the item pointer to include all new items that are now affordable, updating a maxBeauty variable along the way. The maxBeauty at each step is the answer for the current query, which we place in our result array at its original index.
import java.util.Arrays;import java.util.Comparator; class Solution { public int[] maximumBeauty(int[][] items, int[] queries) { // Sort items by price Arrays.sort(items, Comparator.comparingInt(a -> a[0])); // Create indexed queries to keep track of original indices int[][] indexedQueries = new int[queries.length][2]; for (int i = 0; i < queries.length; i++) { indexedQueries[i][0] = queries[i]; indexedQueries[i][1] = i; } // Sort queries by price Arrays.sort(indexedQueries, Comparator.comparingInt(a -> a[0])); int[] answer = new int[queries.length]; int itemIndex = 0; int maxBeauty = 0; // Iterate through sorted queries for (int i = 0; i < queries.length; i++) { int queryPrice = indexedQueries[i][0]; int originalIndex = indexedQueries[i][1]; // Move item pointer and update max beauty for items within budget while (itemIndex < items.length && items[itemIndex][0] <= queryPrice) { maxBeauty = Math.max(maxBeauty, items[itemIndex][1]); itemIndex++; } answer[originalIndex] = maxBeauty; } return answer; }}Complexity
Time
O(N log N + Q log Q). Sorting `items` takes O(N log N). Sorting `indexedQueries` takes O(Q log Q). The two-pointer traversal takes O(N + Q) because each item and each query is visited only once. The total complexity is dominated by the sorting steps.
Space
O(Q) to store `indexedQueries` and the `answer` array.
Trade-offs
Pros
Highly efficient in both time and space.
Often faster in practice than the TreeMap approach due to better memory access patterns and lower constant factors.
Cons
Slightly more complex to implement due to the need to handle original query indices.
Solutions
Solution
class Solution {public int[] maximumBeauty(int[][] items, int[] queries) { Arrays.sort(items, (a, b)->a[0] - b[0]); for (int i = 1; i < items.length; ++i) { items[i][1] = Math.max(items[i - 1][1], items[i][1]); } int n = queries.length; int[] ans = new int[n]; for (int i = 0; i < n; ++i) { int left = 0, right = items.length; while (left < right) { int mid = (left + right) >> 1; if (items[mid][0] > queries[i]) { right = mid; } else { left = mid + 1; } } if (left > 0) { ans[i] = items[left - 1][1]; } } return ans; }}class Solution {public: vector<int> maximumBeauty(vector<vector<int>> &items, vector<int> &queries) { sort(items.begin(), items.end()); for (int i = 1; i < items.size(); ++i) items[i][1] = max(items[i - 1][1], items[i][1]); int n = queries.size(); vector<int> ans(n); for (int i = 0; i < n; ++i) { int left = 0, right = items.size(); while (left < right) { int mid = (left + right) >> 1; if (items[mid][0] > queries[i]) right = mid; else left = mid + 1; } if (left) ans[i] = items[left - 1][1]; } return ans; }};class Solution: def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]: items . sort() prices = [p for p, _ in items] mx = [items[0][1]] for _, b in items[1:]: mx . append(max(mx[- 1], b)) ans = [0] * len(queries) for i, q in enumerate(queries): j = bisect_right(prices, q) if j: ans[i] = mx[j - 1] return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.