2070. Most Beautiful Item for Each Query
Problem Description
In this problem, we have a list of items
, each represented by a pair [price, beauty]
. Our goal is to answer a series of queries, each asking for the maximum beauty value among all items whose price is less than or equal to the query value.
If no items fit the criteria for a given query (all items are more expensive than the query value), the answer for that query is 0
.
We are asked to return a list of the maximum beauty values corresponding to each query.
Intuition
To solve the problem efficiently, we first notice that we can handle the queries independently. So, we want a quick way to find the maximum beauty for any given price limit.
We approach this by sorting the items
by price. Sorting the items allows us to employ a binary search technique to efficiently find the item with the highest beauty below a certain price threshold.
After sorting items
, we create two lists: prices
, which holds the sorted prices, and mx
, which holds the running maximum beauty observed as we iterate through the sorted items. This ensures that for each price prices[i]
, mx[i]
is the maximum beauty of all items with a price less than or equal to prices[i]
.
The binary search is carried out by using the bisect_right
function from Python's bisect
module. For each query, bisect_right
finds the index j
in the sorted prices
list such that all prices to the left of j
are less than or equal to the query value.
If such an index j
is found and is greater than 0
, it means there exists at least one item with a price lower than or equal to the query value. We use j - 1
as the index to get the maximum beauty value from the mx
list.
Otherwise, if no index j
is returned because all items are too expensive, we default the answer for that query to 0
.
This algorithm allows us to answer each query in logarithmic time with respect to the number of items, which is desirable when dealing with a large number of items or queries.
Learn more about Binary Search and Sorting patterns.
Solution Approach
The solution uses a mix of sorting, dynamic programming, and binary search to efficiently answer the maximum beauty queries for given price limits.
Here's the step-by-step implementation strategy:
-
Sorting Items: Start by sorting the
items
based on their price. This is vital because it allows us to leverage binary search later on. Sorting is done using Python's default sorting algorithm, Timsort, which has a time complexity of O(n log n). -
Extracting Prices and Initializing Maximum Beauty List (
mx
):- Extract the sorted prices into a list called
prices
. - Initialize a list
mx
, which keeps track of the maximum beauty encountered so far as we iterate through the items. The first element ofmx
is simply the beauty of the first item in the sorted list.
- Extract the sorted prices into a list called
-
Building a Running Maximum Beauty:
- Iterate through each item, starting from the second one (since the first element's max beauty is already recorded).
- For each item, update the
mx
list with the greater value between the current item's beauty and the last recorded max beauty inmx
. This is a form of dynamic programming, where the result of each step is based on the previous step's result.
-
Answering Queries with Binary Search:
- Initialize an answer list
ans
of the same size asqueries
, defaulting all elements to0
. - For each query, use the
bisect_right
function from thebisect
module to perform a binary search onprices
to find the point where the query value would be inserted while maintaining the list's order.bisect_right
returns an indexj
that is one position past where the query value would be inserted, so a price less than or equal to the query must be at an index beforej
.
- If
j
is not0
, it means an item with a suitable price exists, and the answer for this query ismx[j - 1]
- the corresponding max beauty by that price. Ifj
is0
, it means no items are cheaper than the query, and the answer remains0
.
- Initialize an answer list
-
Return the Answer List:
- After all queries have been processed, return the answer list
ans
filled with the maximum beauties for each respective query.
- After all queries have been processed, return the answer list
This approach effectively decouples the item price-beauty relationship from the queries, by pre-computing a list of maximum beauties (mx
) that can later be quickly referenced using binary search. This transforms what could be an O(n*m) problem (naively checking n items for each of m queries) into an O(n log n + m log n) problem, where n is the number of items and m the number of queries.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example:
Suppose we have the following items
and queries
:
- items = [[3, 2], [5, 4], [3, 1], [10, 7]]
- queries = [2, 4, 6]
Following the steps:
-
Sorting Items:
- We sort
items
by price: sorted_items = [[3, 2], [3, 1], [5, 4], [10, 7]]
- We sort
-
Extracting Prices and Initializing Maximum Beauty List (
mx
):- Extract prices: prices = [3, 3, 5, 10]
- Initialize
mx
with the maximum beauty of the first item: mx = [2]
-
Building a Running Maximum Beauty:
- Process the second item: it has the same price but lower beauty, so
mx
remains the same: mx = [2] - Process the third item: new price with higher beauty, update
mx
: mx = [2, 4] - Process the fourth item: new price with higher beauty, update
mx
: mx = [2, 4, 7]
- Process the second item: it has the same price but lower beauty, so
-
Answering Queries with Binary Search:
- Initialize an answer list
ans
with all zeros: ans = [0, 0, 0] - Query 1: 2 is less than all prices, therefore
ans[0]
remains0
. - Query 2: 4 is equal to the second price,
bisect_right
would place it after index 1, so we usemx[0]
: ans = [0, 2, 0] - Query 3: 6 would fit between indexes 2 and 3,
bisect_right
returns 3 so we usemx[2]
: ans = [0, 2, 4]
- Initialize an answer list
-
Return the Answer List:
- The final answer list reflecting maximum beauties for each query is: ans = [0, 2, 4]
Thus, for the queries
[2, 4, 6], the maximum beauty values for items within these price limits are [0, 2, 4], respectively.
Solution Implementation
1from bisect import bisect_right
2
3class Solution:
4 def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:
5 # Sort the items by price first (since the first item of each sub-list is price)
6 items.sort()
7 # Extract a list of prices for binary search
8 prices = [price for price, _ in items]
9
10 # Create a list to store the maximum beauty encountered so far
11 max_beauty = [items[0][1]] # initialize with the first item's beauty
12 for index in range(1, len(items)):
13 # Update the max_beauty list with the maximum beauty seen up to current index
14 max_beauty.append(max(max_beauty[-1], items[index][1]))
15
16 # Initialize the answer list for the queries with zeroes
17 answers = [0] * len(queries)
18
19 # Process each query to find the maximum beauty for that price
20 for i, query in enumerate(queries):
21 # Find the rightmost item that is not greater than the query price
22 index = bisect_right(prices, query)
23 # If we found an item, store the corresponding max beauty (if not, zero stays by default)
24 if index:
25 answers[i] = max_beauty[index - 1]
26
27 # Return the list of answers to the queries
28 return answers
29
1class Solution {
2 public int[] maximumBeauty(int[][] items, int[] queries) {
3 // Sort the items array based on the price in increasing order
4 Arrays.sort(items, (item1, item2) -> item1[0] - item2[0]);
5
6 // Update the beauty value in the sorted items array to ensure that each
7 // item has the maximum beauty value at or below its price.
8 for (int i = 1; i < items.length; ++i) {
9 // The current maximum beauty is either the beauty of the current item
10 // or the maximum beauty of all previous items.
11 items[i][1] = Math.max(items[i - 1][1], items[i][1]);
12 }
13
14 // The number of queries to process
15 int queryCount = queries.length;
16 // Array to store the answer for each query
17 int[] answers = new int[queryCount];
18
19 // Process each query to find the maximum beauty for the specified price
20 for (int i = 0; i < queryCount; ++i) {
21 // Use binary search to find the rightmost item with a price not
22 // exceeding the query (price we can spend).
23 int left = 0, right = items.length;
24 while (left < right) {
25 int mid = (left + right) >> 1; // equivalent to (left + right) / 2
26 if (items[mid][0] > queries[i]) {
27 // If the mid item's price exceeds the query price, move the right pointer
28 right = mid;
29 } else {
30 // Otherwise, move the left pointer to continue searching to the right
31 left = mid + 1;
32 }
33 }
34
35 // If there's at least one item that costs less than or equal to the query price
36 if (left > 0) {
37 // The answer is the maximum beauty found among all the affordable items
38 answers[i] = items[left - 1][1];
39 }
40 // If no such item is found, the default answer of 0 (for beauty) will remain
41 }
42
43 // Return the array of answers for all the queries
44 return answers;
45 }
46}
47
1#include <vector>
2#include <algorithm>
3using namespace std;
4
5class Solution {
6public:
7 // Function that returns the maximum beauty item that does not exceed the query price
8 vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {
9 // Sort items based on their price in ascending order
10 sort(items.begin(), items.end());
11
12 // Preprocess items to keep track of the maximum beauty so far at each price point
13 for (int i = 1; i < items.size(); ++i) {
14 items[i][1] = max(items[i - 1][1], items[i][1]);
15 }
16
17 int numOfQueries = queries.size();
18 vector<int> answers(numOfQueries);
19
20 // Iterate over each query to find the maximum beauty that can be obtained
21 for (int i = 0; i < numOfQueries; ++i) {
22 int left = 0, right = items.size();
23
24 // Perform a binary search to find the rightmost item with price less than or equal to the query price
25 while (left < right) {
26 int mid = (left + right) / 2;
27 if (items[mid][0] > queries[i])
28 right = mid; // Item is too expensive, reduce the search range
29 else
30 left = mid + 1; // Item is affordable, potentially look for more expensive items
31 }
32
33 // If search ended with left pointing to an item, take the beauty value of the item to the left of it
34 // because the binary search gives us the first item with a price higher than the query
35 if (left > 0) answers[i] = items[left - 1][1];
36 // If left is 0, then all items are too expensive, thus the answer for this query is 0 by default
37 }
38
39 return answers;
40 }
41};
42
1// Import necessary functions from 'lodash' for sorting and binary search
2import _ from 'lodash';
3
4// Function that returns the maximum beauty item that does not exceed the query price
5function maximumBeauty(items: number[][], queries: number[]): number[] {
6 // Sort items based on their price in ascending order
7 items.sort((a, b) => a[0] - b[0]);
8
9 // Preprocess items to keep track of the maximum beauty so far at each price point
10 for (let i = 1; i < items.length; ++i) {
11 items[i][1] = Math.max(items[i - 1][1], items[i][1]);
12 }
13
14 let numOfQueries = queries.length;
15 let answers = new Array(numOfQueries).fill(0);
16
17 // Iterate over each query to find the maximum beauty that can be obtained
18 for (let i = 0; i < numOfQueries; ++i) {
19 let left = 0, right = items.length;
20
21 // Perform a binary search to find the rightmost item with price less than or equal to the query price
22 while (left < right) {
23 let mid = Math.floor((left + right) / 2);
24 if (items[mid][0] > queries[i])
25 right = mid; // Item is too expensive, reduce the search range
26 else
27 left = mid + 1; // Item is affordable, potentially look for more expensive items
28 }
29
30 // If search ended with left pointing to an item, take the beauty value of the item to the left of it
31 // because the binary search gives us the first item with a price higher than the query
32 if (left > 0) {
33 answers[i] = items[left - 1][1];
34 }
35 // If left is 0, then all items are too expensive, thus the answer for this query is 0 by default
36 }
37
38 return answers;
39}
40
Time and Space Complexity
Time Complexity
The time complexity of the provided code can be broken down into the following parts:
-
Sorting the
items
list: Theitems.sort()
method is called on the list of items, which typically has a time complexity ofO(n * log(n))
, wheren
is the number of items. -
Creating the
prices
list: This involves iterating over the sorteditems
list to build a new list of prices, which will takeO(n)
. -
Creating the
mx
list: A single for-loop is used to construct themx
list. This also runs inO(n)
time as it iterates overn
items once. -
Answering the queries by binary search: Each query performs a binary search to find the right index in the
prices
list, which takesO(log(n))
. Since this is done forq
queries, the total time complexity for this step isO(q * log(n))
.
Combining these steps, the overall time complexity is O(n * log(n) + n + n + q * log(n))
, which simplifies to O(n * log(n) + q * log(n))
because the linear terms are overshadowed by the n * log(n)
term when n
is large.
Space Complexity
The space complexity of the code can be analyzed by considering the additional data structures used:
-
The
prices
list: This consumesO(n)
space. -
The
mx
list: This also consumesO(n)
space. -
The
ans
list: Space needed isO(q)
for storing the answers forq
queries.
Therefore, the overall space complexity is O(n + n + q)
which simplifies to O(n + q)
as we add the space required for the two lists related to items and the space for the answers to the queries.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following shows the order of node visit in a Breadth-first Search?
Recommended Readings
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.