Most Beautiful Item for Each Query Solution In C++/Java/Python/JS
Problem Description:
You are given a 2D integer array items where items[i] = [priceᵢ, beautyᵢ] 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.
Examples:
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.
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.
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 <= 105
- items[i].length == 2
- 1 <= or , beauty[i], queries[j] <= 109
Brute Force Approach
Most Beautiful Item for Each Query Description:
We are given:
- A list of items, where each item is represented as [price, beauty].
- A list of queries, where each query tells us the maximum price we can afford.
Goal:
For each query, we need to find the maximum beauty of any item whose price is less than or equal to the query value.
Finally, we return an array where each element is the answer for the corresponding query.
Let's think about how to solve this step-by-step:
- We have a list of items with their prices and beauty values.
- For each query, we want to find the most beautiful item that we can afford.
Imagine we are at some queries[j]. To find the answer to this query, we need to check each item one by one. For every item, we compare its price with the current query value. If the item's price is less than or equal to queries[j], we compare its beauty with the current maximum beauty we have found so far. If the item's beauty is greater, we update our maximum beauty value.
Most Beautiful Item for Each Query Algorithm
Input: items = [[1, 2], [3, 2], [2, 4], [5, 6]] queries = [1, 2, 3]
Output: [2, 4, 4]
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, the items which can be considered are [1,2], [3,2] and [2,4]
Step 1: Initialization
We have 4 items and 3 queries.
- n = items.size() → n = 4 (since there are 4 items)
- m = queries.size() → m = 3 (since there are 3 queries)
- ans[] → An empty vector to store the results
Step 2: First Query → queries[0] = 1
We need to find the most beautiful item whose price is less than or equal to 1.
- Initialize maxBeauty = 0.
- Start iterating over the items:
- First item is [1, 2]. Its price 1 is less than or equal to the query value 1, so we update maxBeauty to 2.
- Second item is [3, 2]. Its price 3 is greater than 1, so we skip it.
- Third item is [2, 4]. Its price 2 is greater than 1, so we skip it.
- Fourth item is [5, 6]. Its price 5 is greater than 1, so we skip it.
- After checking all the items, the highest beauty we can afford for this query is 2.
- Append 2 to ans[].
- ans[] becomes [2].
Step 3: Second Query → queries[1] = 2
We need to find the most beautiful item whose price is less than or equal to 2.
- Initialize maxBeauty = 0.
- Start iterating over the items:
- First item is [1, 2]. Its price 1 is less than or equal to 2, so we update maxBeauty to 2.
- Second item is [3, 2]. Its price 3 is greater than 2, so we skip it.
- Third item is [2, 4]. Its price 2 is equal to the query value, and its beauty 4 is greater than the current maxBeauty (2), so we update maxBeauty to 4.
- Fourth item is [5, 6]. Its price 5 is greater than 2, so we skip it.
- After checking all the items, the highest beauty we can afford for this query is 4.
- Append 4 to ans[].
- ans[] becomes [2, 4].
Step 4: Third Query → queries[2] = 3
We need to find the most beautiful item whose price is less than or equal to 3.
- Initialize maxBeauty = 0.
- Start iterating over the items:
- First item is [1, 2]. Its price 1 is less than or equal to 3, so we update maxBeauty to 2.
- Second item is [3, 2]. Its price 3 is equal to the query value, but its beauty 2 is not greater than the current maxBeauty (2), so no change.
- Third item is [2, 4]. Its price 2 is less than 3, and its beauty 4 is greater than the current maxBeauty (2), so we update maxBeauty to 4.
- Fourth item is [5, 6]. Its price 5 is greater than 3, so we skip it.
- After checking all the items, the highest beauty we can afford for this query is 4.
- Append 4 to ans[].
- ans[] becomes [2, 4, 4].
Final Output:
The final result is: [2, 4, 4]
Most Beautiful Item for Each Query Algorithm
Step 1: Initialization
- Create two integer variables:
- n → Number of items → items.size()
- m → Number of queries → queries.size()
2. Create an empty array ans[] to store the answers.
Step 2: Loop Over Each Query
- Start a loop that runs from j = 0 to m - 1 (for each query).
- Inside the loop, initialize a variable maxBeauty = 0 to keep track of the maximum beauty value for the current query.
Step 3: Loop Over Each Item
- Start another loop that runs from i = 0 to n - 1 (for each item).
- For each item, check if its price is less than or equal to the current query value, if yes then maximize the maxBeauty variable.
Step 4: Store the Result
- After checking all items for the current query, store the highest beauty value into the answer array
Step 5: Return the Result
- After processing all queries, return the answer array ans[].
Most Beautiful Item for Each Query Solution
Most Beautiful Item for Each Query Solution in C++
class Solution {
public:
// Function to find the maximum beauty for each query
vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {
int n = items.size();
int m = queries.size();
// Stores the final answers for each query
vector<int> ans;
// Iterate over each query
for (int j = 0; j < m; ++j) {
int maxBeauty = 0;
// Check each item to find the max beauty within the price limit
for (int i = 0; i < n; ++i) {
if (items[i][0] <= queries[j]) {
maxBeauty = max(maxBeauty, items[i][1]);
}
}
// Store the result for this query
ans.push_back(maxBeauty);
}
return ans;
}
};Most Beautiful Item for Each Query Solution in Java
class Solution {
// Function to compute maximum beauty for each query
public List<Integer> maximumBeauty(int[][] items, int[] queries) {
int n = items.length;
int m = queries.length;
// Stores the result for each query
List<Integer> ans = new ArrayList<>();
// Iterate over each query
for (int j = 0; j < m; j++) {
int maxBeauty = 0;
// Iterate over items to find the max beauty within the price range
for (int i = 0; i < n; i++) {
if (items[i][0] <= queries[j]) {
maxBeauty = Math.max(maxBeauty, items[i][1]);
}
}
// Store the result
ans.add(maxBeauty);
}
return ans;
}
}Most Beautiful Item for Each Query Solution in Python
class Solution:
def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:
n = len(items)
m = len(queries)
# Stores the result for each query
ans = []
# Iterate over each query
for j in range(m):
max_beauty = 0
# Iterate over items to find the max beauty within the price range
for i in range(n):
if items[i][0] <= queries[j]:
max_beauty = max(max_beauty, items[i][1])
# Store the result
ans.append(max_beauty)
return ansMost Beautiful Item for Each Query Solution in Javascript
/**
* @param {number[][]} items
* @param {number[]} queries
* @return {number[]}
*/
var maximumBeauty = function(items, queries) {
let n = items.length;
let m = queries.length;
// Stores the result for each query
let ans = [];
// Iterate over each query
for (let j = 0; j < m; j++) {
let maxBeauty = 0;
// Iterate over items to find the max beauty within the price range
for (let i = 0; i < n; i++) {
if (items[i][0] <= queries[j]) {
maxBeauty = Math.max(maxBeauty, items[i][1]);
}
}
// Store the result
ans.push(maxBeauty);
}
return ans;
}Most Beautiful Item for Each Query Complexity Analysis
Time Complexity: O(m×n)
Let's break down the time complexity step-by-step:
Outer Loop:
- We have a loop that runs for each query → m queries
- So, the outer loop contributes O(m)
Inner Loop:
- For each query, we check every item → n items
- So, the inner loop contributes O(n)
Max Operation:
- max() operation is constant time → O(1)
Therefore, the total time complexity becomes: O(m)×O(n)=O(m×n)
Final Time Complexity: O(m×n)
Space Complexity: O(n+m)
Auxiliary Space Complexity:
Auxiliary space refers to the extra space used by the algorithm (apart from the input):
- Answer Array O(m)
- We store the result for each query in an array of size m.
- Therefore, the auxiliary space used by ans[] is: O(m)
- Other Variables
- We use a few integer variables like n, m, maxBeauty, and loop variables.
- These take constant space → O(1)
Total Space Complexity:
Input space is not counted as part of auxiliary space, but it's good to mention it for total space calculation:
- Items Array: O(n)
- We are given n items, each with two values (price and beauty).
- So the input space for items[][] is: O(n)
- Queries Array: O(m)
- We are given m queries.
- So the input space for queries[] is: O(m)
Total space = Auxiliary space + Input space
O(m)+O(n)+O(m)=O(n+m)
Is the brute force approach efficient?
The time complexity of the brute force approach is O(m × n), where m is the size of the queries array and n is the size of the items array. Since m, n ≤ 105, the total number of operations in the worst case can reach up to 10¹⁰.
To put this into perspective, a computer can handle roughly 10⁶ operations in one second. So, if our code needs to perform 10¹⁰ operations, it would take around 10,000 seconds (which is almost 3 hours!) to complete. 😬
Clearly, this is way too slow and not practical for real-world use. That’s why we need to find a more efficient approach to solve this problem. Let’s see how we can improve it!
Optimal Approach
Intuition:
The time complexity of the brute force approach is O(m × n). Let's think about how we can make this more efficient.
We know that we have to go through each query since we need to calculate an answer for every query. So, reducing the query loop isn’t possible — we have to run it m times.
But what about the inner loop? Instead of checking every item for each query, can we somehow organise or preprocess the items to make this faster? If we figure out a way to avoid checking every single item for each query, we can reduce the n part of the complexity — and that’s where the real improvement will come from!
According to the problem statement, for each query, we need to find the item with the maximum beauty at a price less than or equal to query[j].
Now, what if we sort the items array by price?
- If the items are sorted by price, we can efficiently find the best possible item for any given price using a more structured approach.
- If the array is sorted, picking any element gives us a clear idea of where to look next. For example, if the price of an item is greater than the current query, we know that all the elements after it will also have a greater price, so we can stop there or avoid checking them altogether.
- This way, instead of scanning the entire list for every query, we can directly focus on the range where the answer lies, saving a lot of unnecessary work.
But we are not done here. theabout the beauty values?. Can we build something on the basis of it that can help us in future?.
Since we only care about the maximum beauty for a given price range, we can create a new array called maxBeauty[] to simplify things:
- maxBeauty[i] will store the highest beauty we’ve seen so far from index 0 to i in the sorted items array with respect to price.
- Since the array is sorted by price, the price of the maximum beauty stored at maxBeauty[i] will naturally be less than or equal to price[i].
- This way, once maxBeauty[] is ready, we don’t need to search through the items repeatedly — we can simply check the highest beauty available for any price[i] less than or equal to queries[j] directly looking at the maxBeauty[i].
By building this maxBeauty[] array, we make the problem much easier to solve and significantly speed up the query processing!
Now we know everything to solve this problem. To summarise it first we need to sort the items array, then compute the maxBeauty array and then operate over queries.
How to compute the maxBeauty array?
To compute maxBeauty. First, we have to sort the items[] array based on price. We can then set maxBeauty[0] to the beauty of the first item since it’s the only element we’ve seen so far.
After that, we can iterate through the rest of the array. For each index i, maxBeauty[i] will be the maximum of maxBeauty[i - 1] (maximum beauty found so far), the beauty value at the current index i.
This way, maxBeauty[i] will always store the highest beauty we can get with a price less than or equal to price[i].
Example:
Let's say we have the following sorted items.
items = [[2, 5], [4, 3], [6, 10], [8,7]]
- First item has price 2 and beauty 5 → maxBeauty[0] = 5
- Second item has price 4 and beauty 3 → Previous maximum beauty is 5, so maxBeauty[1] = max(5, 3) = 5
- Third item has price 6 and beauty 10 → Previous maximum beauty is 5, so maxBeauty[2] = max(5, 10) = 10
- Fourth item has price 8 and beauty 7 → Previous maximum beauty is 10, so maxBeauty[3] = max(10, 7) = 10
maxBeauty = [5, 5, 10, 10]
We are done with the precomputing part now, let's focus on the part where we need to operate on the queries.
How to make use of the sorted items array with respect to price and the maxBeauty array in every query?
For every query, our goal is to find the index of the largest value of price[i] that is less than or equal to queries[j].
If we can efficiently find this index (idx), we can directly get the answer from the maxBeauty[] array.
Why does this work? Because maxBeauty[idx] already stores the highest beauty for all prices less than or equal to price[idx].
Therefore, once we know the index idx, the answer to the query becomes maxBeauty[idx]; no need to manually search for the maximum beauty anymore!
The real challenge here is how to find this index quickly.
How to find the index of the largest value of price[i] less than or equal to queries[j]?
We know that the items array is sorted, and we can't iterate through every item to find the required index.
Let’s focus on the middle index (mid) of the items array
To find the index of the largest value of price[mid] which is less than or equal to queries[j], we have two possible cases based on the comparison between price[mid] and queries[j]:
Case 1: If price[i] is less than equal to queries[j]
- In this case, the current element at mid might be a potential answer, but there could be a better option on the right side.
- This is because if price[mid] <= queries[j], any element to the left of mid will also satisfy the condition, but we want the largest possible price that is still within the limit of queries[j].
- Therefore, we move our search to the right side to see if there’s a larger valid price.
Example:
queries[j] = 6, sorted items = [[2, 5], [4, 3], [6, 10], [8, 7]].
The mid is 1 here. If items[mid][0] = 4 (price[mid]), we have a valid answer, but we check the right side to see if we can find a better one.
Case 2: If price[mid] is greater than queries[j]
- If the current element at mid is greater than queries[j], it’s definitely not a valid answer.
- Since the array is sorted by price, all elements to the right of mid will also have a price greater than queries[j].
- Therefore, we move our search to the left side to find a smaller or equal price.
Example:
queries[j] = 3, sorted items = [[2, 5], [4, 3], [6, 10], [8, 7]].
If items[mid][0] = 4 (price[mid]), it’s greater than 3, so we look to the left side for a smaller value
Most Beautiful Item for Each Query Algorithm
To do this, we can declare two pointers, low and high, which will initially point to the start (0) and end (n - 1) of the sorted items array, covering the entire search space.
Then we initialise idx to -1. At the end of the process, it will store the index of the largest price less than or equal to queries[j].
The idea is to gradually reduce the search space based on the value at the middle index (mid).
We'll calculate mid, which is nothing but the average of low and high.
At each step, we'll compare the price at items[mid][0] with queries[j]:
- If items[mid][0] <= queries[j], it means the current element is a valid option, but we want to check if there's a better one on the right side. So, we shift the low pointer to mid + 1 to search further on the right.
- If items[mid][0] > queries[j], it means the current element and all elements to the right are greater than queries[j], so we need to search on the left side. Therefore, we shift the high pointer to mid-1.
This process continues until the search space is exhausted (i.e., low exceeds high).
If we find a valid index during this process, we can directly use maxBeauty[idx] as our answer for that query.
This approach helps reduce the search space effectively, leading to a much faster solution compared to the brute force approach.
This method of narrowing down the search space by computing on the basis of the middle index is called binary search. It is much faster than linear search.
Here you can read about binary search in more detail.
Animation Showing How Optimal Approach works.
Most Beautiful Item for Each Query Example
Input: items = [[1, 2], [3, 2], [2, 4], [5, 6]] queries = [1, 2, 3]
Output: [2, 4, 4]
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, the items which can be considered are [1,2], [3,2] and [2,4]
Step 1: Initialization
We are given:
- Items: [[1, 2], [3, 2], [2, 4], [5, 6]] → Each pair represents [price, beauty].
- Queries: [1, 2, 3] → Each query represents the maximum price we can afford.
- Goal: For each query, find the maximum beauty of items whose price is ≤ query price.
Step 2: Sorting Items by Price
To efficiently search for the highest beauty within a price range, we sort items by price in ascending order:
- Before sorting: [[1, 2], [3, 2], [2, 4], [5, 6]]
- After sorting: [[1, 2], [2, 4], [3, 2], [5, 6]]
This ensures that for any query, items with lower prices appear earlier in the list, making it easier to determine the best affordable beauty.
Step 3: Building the maxBeauty Array
To quickly determine the highest beauty for any price range, we create a prefix maximum beauty array (maxBeauty), where each index i stores the maximum beauty encountered from index 0 to i.
- At index 0, beauty is 2, so maxBeauty[0] = 2.
- At index 1, compare previous max 2 with new beauty 4 → maxBeauty[1] = 4.
- At index 2, compare previous max 4 with new beauty 2 → maxBeauty[2] = 4.
- At index 3, compare previous max 4 with new beauty 6 → maxBeauty[3] = 6.
Final maxBeauty array: [2, 4, 4, 6]
This means:
- maxBeauty[0] = 2 → Best beauty for price ≤ 1 is 2.
- maxBeauty[1] = 4 → Best beauty for price ≤ 2 is 4.
- maxBeauty[2] = 4 → Best beauty for price ≤ 3 is 4.
- maxBeauty[3] = 6 → Best beauty for price ≤ 5 is 6.
Step 4: Answering Each Query Using Efficient Search
For each query, we need to find the rightmost index in the sorted items list where price ≤ query.
We do this using two pointers (low and high) to efficiently search for this index.
Processing Query = 1
- We need to find the highest price ≤ 1.
- Initialize: low = 0, high = 3 (searching in the full sorted array).
- First search step:
- mid = (0 + 3) / 2 = 1 → items[1] = [2, 4].
- 2 > 1, so we discard the right half and move high = 0.
- Second search step:
- mid = (0 + 0) / 2 = 0 → items[0] = [1, 2].
- 1 ≤ 1, so we store idx = 0 and move low = 1 to check for better answers.
- Search stops since low > high.
- Final index found = 0, meaning the best beauty is maxBeauty[0] = 2.
- Answer for this query = 2.
Processing Query = 2
- We need to find the highest price ≤ 2.
- Initialize: low = 0, high = 3.
- First search step:
- mid = (0 + 3) / 2 = 1 → items[1] = [2, 4].
- 2 ≤ 2, so we store idx = 1 and move low = 2 to check for better answers.
- Second search step:
- mid = (2 + 3) / 2 = 2 → items[2] = [3, 2].
- 3 > 2, so we discard the right half and move high = 1.
- Search stops since low > high.
- Final index found = 1, meaning the best beauty is maxBeauty[1] = 4.
- Answer for this query = 4.
Processing Query = 3
- We need to find the highest price ≤ 3.
- Initialize: low = 0, high = 3.
- First search step:
- mid = (0 + 3) / 2 = 1 → items[1] = [2, 4].
- 2 ≤ 3, so we store idx = 1 and move low = 2 to check for better answers.
- Second search step:
- mid = (2 + 3) / 2 = 2 → items[2] = [3, 2].
- 3 ≤ 3, so we store idx = 2 and move low = 3 to check for better answers.
- Search stops since low > high.
- Final index found = 2, meaning the best beauty is maxBeauty[2] = 4.
- Answer for this query = 4.
Step 5: Final Output
After processing all queries, we get the output:
[2, 4, 4].
Most Beautiful Item for Each Query Algorithm
Step 1: Sort the items Array by Price
- Since searching for the largest affordable price is easier in a sorted array, we first sort items based on price.
- Sorting ensures that all lower-priced items come first, making it easier to track the maximum beauty.
Step 2: Construct the maxBeauty Array
- We need to efficiently find the best beauty for any given price.
- We iterate through the sorted items array and maintain a maxBeauty array where:
- maxBeauty[i] = max(maxBeauty[i-1], beauty[i])
- This ensures maxBeauty[i] always stores the highest beauty seen so far.
Step 3: Process Each Query Efficiently
- For each query, we need to find the largest price ≤ query.
- We use efficient searching to find the rightmost index in items where price ≤ query.
- Once found, maxBeauty[idx] gives the answer.
Step 4: Implement Efficient Searching
- Use two pointers (low and high) to efficiently locate the rightmost valid index.
- If items[mid][0] ≤ query, store idx = mid (potential answer) and move low to mid + 1 to search for a better index.
- If items[mid][0] > query, move high to mid - 1.
Step 5: Handle Edge Cases
- If no item is affordable (idx = -1), return 0 for that query.
- If all items are affordable, return the max beauty from maxBeauty[idx].
Most Beautiful Item for Each Query Leetcode Solution
Most Beautiful Item for Each Query Solution in C++
class Solution {
public:
// Function to compute the maximum beauty for each query
vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {
int n = items.size();
int m = queries.size();
// Sort items by price in ascending order
sort(items.begin(), items.end());
// Create a maxBeauty array to store the highest beauty seen so far
vector<int> maxBeauty(n);
maxBeauty[0] = items[0][1];
// Compute maxBeauty for each item
for (int i = 1; i < n; ++i) {
maxBeauty[i] = max(maxBeauty[i - 1], items[i][1]);
}
// Stores results for each query
vector<int> ans;
// Process each query
for (int j = 0; j < m; ++j) {
int low = 0, high = n - 1;
int idx = -1;
// Search for the highest index where price <= queries[j]
while (low <= high) {
int mid = (low + high) / 2;
if (items[mid][0] <= queries[j]) {
idx = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
// If no valid price is found, return 0, otherwise return maxBeauty[idx]
ans.push_back(idx == -1 ? 0 : maxBeauty[idx]);
}
return ans;
}
};Most Beautiful Item for Each Query Solution in Java
class Solution {
// Function to compute the maximum beauty for each query
public List<Integer> maximumBeauty(int[][] items, int[] queries) {
int n = items.length;
int m = queries.length;
// Sort items by price in ascending order
Arrays.sort(items, Comparator.comparingInt(a -> a[0]));
// Create a maxBeauty array to store the highest beauty seen so far
int[] maxBeauty = new int[n];
maxBeauty[0] = items[0][1];
// Compute maxBeauty for each item
for (int i = 1; i < n; i++) {
maxBeauty[i] = Math.max(maxBeauty[i - 1], items[i][1]);
}
// Stores results for each query
List<Integer> ans = new ArrayList<>();
// Process each query
for (int j = 0; j < m; j++) {
int low = 0, high = n - 1;
int idx = -1;
// Search for the highest index where price <= queries[j]
while (low <= high) {
int mid = (low + high) / 2;
if (items[mid][0] <= queries[j]) {
idx = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
// If no valid price is found, return 0, otherwise return maxBeauty[idx]
ans.add(idx == -1 ? 0 : maxBeauty[idx]);
}
return ans;
}
}Most Beautiful Item for Each Query Solution in Python
class Solution:
def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:
n = len(items)
m = len(queries)
# Sort items by price in ascending order
items.sort()
# Create maxBeauty array to store the highest beauty seen so far
max_beauty = [0] * n
max_beauty[0] = items[0][1]
# Compute maxBeauty for each item
for i in range(1, n):
max_beauty[i] = max(max_beauty[i - 1], items[i][1])
# Stores results for each query
ans = []
# Process each query
for q in queries:
low, high = 0, n - 1
idx = -1
# Search for the highest index where price <= query
while low <= high:
mid = (low + high) // 2
if items[mid][0] <= q:
idx = mid
low = mid + 1
else:
high = mid - 1
# If no valid price is found, return 0, otherwise return maxBeauty[idx]
ans.append(0 if idx == -1 else max_beauty[idx])
return ansMost Beautiful Item for Each Query Solution in Javascript
/**
* @param {number[][]} items
* @param {number[]} queries
* @return {number[]}
*/
var maximumBeauty = function(items, queries) {
let n = items.length;
let m = queries.length;
// Sort items by price in ascending order
items.sort((a, b) => a[0] - b[0]);
// Create maxBeauty array to store the highest beauty seen so far
let maxBeauty = Array(n).fill(0);
maxBeauty[0] = items[0][1];
// Compute maxBeauty for each item
for (let i = 1; i < n; i++) {
maxBeauty[i] = Math.max(maxBeauty[i - 1], items[i][1]);
}
// Stores results for each query
let ans = [];
// Process each query
for (let q of queries) {
let low = 0, high = n - 1, idx = -1;
// Search for the highest index where price <= query
while (low <= high) {
let mid = Math.floor((low + high) / 2);
if (items[mid][0] <= q) {
idx = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
// If no valid price is found, return 0, otherwise return maxBeauty[idx]
ans.push(idx === -1 ? 0 : maxBeauty[idx]);
}
return ans;
}Most Beautiful Item for Each Query Complexity Analysis
Time Complexity: O((n+m)logn))
Step 1: Sorting the items Array
Before processing the queries, we sort the items array based on price.
- Sorting takes O(n log n) using an efficient algorithm like MergeSort or QuickSort.
- Time Complexity for Sorting: O(n log n)
Step 2: Constructing maxBeauty Array
After sorting, we iterate through the items array once to compute the maxBeauty array.
- The maxBeauty array stores the highest beauty seen so far for each price.
- This requires a single O(n) pass through the array, updating maxBeauty[i] as: maxBeauty[i]=max(maxBeauty[i−1],items[i][1])
- Time Complexity for Constructing maxBeauty: O(n)
Step 3: Processing Queries with Binary Search
For each query, we need to find the index of the rightmost item with a price ≤ queries[j].
Instead of iterating over all items (which would take O(n) per query), we use binary search to speed up the process.
Understanding Binary Search Complexity
- Binary search works by dividing the search space in half at each step.
- We start with low = 0 and high = n-1.
- At each step, we calculate mid = (low + high) / 2 and check if items[mid][0] is ≤ queries[j].
- If items[mid][0] ≤ queries[j], we move right (low = mid + 1) to find a better answer.
- Otherwise, we move left (high = mid - 1).
- This reduces the search space exponentially.
- Since the search space is halved at each step, binary search runs in O(log n) time.
- Example: If we have n = 100000, the number of steps taken by binary search is roughly log₂(100000) ≈ 17 steps, which is much faster than O(n) ≈ 100000 steps.
- Time Complexity for Each Query: O(log n)
Since there are m queries, the total time complexity for query processing is:
- Total Query Processing Time: O(m log n)
Final Complexity Calculation
Now, summing up all the parts:
- Sorting the items array: O(n log n)
- Constructing maxBeauty array: O(n)
- Processing m queries using binary search: O(m log n)
Final Time complexity: O(nlogn)+O(n)+O(mlogn) = O((n+m)logn)
Space Complexity: O(n+m)
Auxiliary Space Complexity (Extra Space Used)
Auxiliary space refers to the additional memory used beyond the input storage.
- We store the maximum beauty seen so far for each item in a separate maxBeauty array.
- Since there are n items, this takes O(n) space.
- The ans array stores the final answers for m queries.
- Since there are m queries, this takes O(m) space.
So, the total auxiliary space complexity is O(n) + O(m) = O(n + m).
3. Total Space Complexity (Including Input Storage)
Input Storage Space
The input itself consists of:
- items array, which stores n items (each containing two values: price and beauty).
- This takes O(n) space.
- queries array, which contains m queries.
- This takes O(m) space.
Since this space is part of the input, it is not counted in auxiliary space.
Total space complexity is the sum of input storage and auxiliary space:
Total Space Complexity=Input Storage + Auxiliary space:
O(n)+O(m)+O(n+m)= O(n+m)
Similar Problems
Now we have successfully tackled this problem, let's try these similar problems:-
1. Closest Room
There is a hotel with n rooms. The rooms are represented by a 2D integer array rooms where rooms[i] = [roomId_i, size_i] denotes that there is a room with room number roomIdi and size equal to size_i. Each roomId_i is guaranteed to be unique.
You are also given k queries in a 2D array queries where queries[j] = [preferred_j, minSize_j)]. The answer to the jth query is the room number id of a room such that:
- The room has a size of at least minSize_j, and
- abs(id - preferred_j) is minimized, where abs(x) is the absolute value of x.
If there is a tie in the absolute difference, then use the room with the smallest such id. If there is no such room, the answer is -1.
Return an array answer of length k where answer[j] contains the answer to the jth query.
We define the conversion array conver of an array arr as follows:
- conver[i] = arr[i] + max(arr[0..i]) where max(arr[0..i]) is the maximum value of arr[j] over 0 <= j <= i.
We also define the score of an array arr as the sum of the values of the conversion array of arr.
Given a 0-indexed integer array nums of length n, return an array ans of length n where ans[i] is the score of the prefix nums[0..i].
You are given two 0-indexed integer arrays nums1 and nums2, each of length n, and a 1-indexed 2D array queries where queries[i] = [x_i, y_i].
For the ith query, find the maximum value of nums1[j] + nums2[j] among all indices j (0 <= j < n), where nums1[j] >= x_i and nums2[j] >= y_i, or -1 if there is no j satisfying the constraints.
Return an array answer where answer[i] is the answer to the ith query.