• Posts

Problem 2070 Most Beautiful Item for Each Query

Problem Statement

Link - Problem 2070

Question

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 <= 105
• items[i].length == 2
• 1 <= pricei, beautyi, queries[j] <= 109

Solution

class Solution {
public:
    vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {
        vector<int> ans(queries.size());

        sort(items.begin(), items.end(),[](vector<int>& a, vector<int>& b) { return a[0] < b[0]; });

        int max_beauty = items[0][1];
        for (int i = 0; i < items.size(); i++) {
            max_beauty = max(max_beauty, items[i][1]);
            items[i][1] = max_beauty;
        }

        for (int i = 0; i < queries.size(); i++) {
            ans[i] = binarySearch(items, queries[i]);
        }

        return ans;
    }

    int binarySearch(vector<vector<int>>& items, int targetPrice) {
        int left = 0;
        int right = items.size() - 1;
        int max_beauty = 0;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (items[mid][0] > targetPrice) {
                right = mid - 1;
            } else {
                max_beauty = max(max_beauty, items[mid][1]);
                left = mid + 1;
            }
        }
        return max_beauty;
    }
};

Complexity Analysis

| Algorithm                        | Time Complexity | Space Complexity |
| -------------------------------- | --------------- | ---------------- |
| Binary Search with Preprocessing | O(n log n)      | O(n)             |

Explanation

Intial Thoughts

My initial thought was to approach this problem by identifying the relationship between the price and beauty of each item, then using that relationship to quickly find the maximum beauty for each query. The problem requires us to find the maximum beauty of an item for each query where the price is less than or equal to the query price. I realized that sorting the items by price could be useful in efficiently finding the maximum beauty for each query. I also noticed that there could be a connection between binary search and the sorted items, which could solve the problem efficiently. Lastly, I considered using dynamic programming to build up a solution by considering the previous items

Intuitive Analysis

My intuition on this problem is that by sorting the items and using a modified binary search or lower-bound approach, we can efficiently find the maximum beauty for each query. I also thought to update the beauty of each item with the maximum beauty seen so far as we iterate through the sorted items, which would make the binary search even more efficient. By doing this, we ensure that the beauty of each item is the maximum beauty of all items with price less than or equal to its own price. This approach allows us to avoid redundant comparisons and directly find the maximum beauty for each query. Another key insight was to initialize the beauty of each item with its own beauty, and then update it as we iterate through the sorted items. This ensures that the binary search can efficiently find the maximum beauty for each query.

1. Intuition

• The problem can be solved by first sorting the items based on their prices.
• Then, we can iterate through the sorted items and keep track of the maximum beauty encountered so far.
• This maximum beauty will be the answer for all queries with a price greater than or equal to the current item’s price.
• To find the answer for a query, we can use binary search to find the largest price that is less than or equal to the query price.
• The maximum beauty at this index will be the answer for the query.
• This approach works because the items are sorted by price, and the maximum beauty is updated as we iterate through the items.
• This ensures that the maximum beauty at each index is the maximum beauty of all items with a price less than or equal to the current item’s price.

2. Implementation

• The sort function is used to sort the items based on their prices: sort(items.begin(), items.end(),[](vector<int>& a, vector<int>& b) { return a[0] < b[0]; });
• The max_beauty variable is used to keep track of the maximum beauty encountered so far: int max_beauty = items[0][1];
• The binarySearch function is used to find the largest price that is less than or equal to the query price: int binarySearch(vector<vector<int>>& items, int targetPrice) { ... }
• The binarySearch function uses a binary search approach to find the largest price: while (left <= right) { ... }
• The binarySearch function returns the maximum beauty at the index found: return max_beauty;
• The maximumBeauty function iterates through the queries and calls the binarySearch function for each query: for (int i = 0; i < queries.size(); i++) { ... }
• The maximumBeauty function returns the answers for all queries: return ans;

Complexity Analysis

Time Complexity:

• The algorithm can be divided into three main steps: sorting, preprocessing, and binary search. The sorting step sort(items.begin(), items.end(),[](vector<int>& a, vector<int>& b) { return a[0] < b[0]; }); has a time complexity of O(n log n), where n is the number of items.
• The preprocessing step for (int i = 0; i < items.size(); i++) { ... } has a time complexity of O(n), where n is the number of items.
• The binary search step for (int i = 0; i < queries.size(); i++) { ... } has a time complexity of O(m log n), where m is the number of queries. Since m can be less than or equal to n, we can simplify this to O(n log n) and this dominant operation justifies the overall time complexity classification of O(n log n).

Space Complexity:

• The algorithm requires additional space to store the result vector<int> ans(queries.size()); which has a space complexity of O(m), where m is the number of queries.
• The space required to store the items and queries also contributes to the overall space complexity of O(n + m), where n is the number of items and m is the number of queries.
• However, since n can be greater than or equal to m, we can simplify the overall space complexity to O(n), justifying the space complexity classification.

Footnote

This question is rated as Medium difficulty.

Hints

Can we process the queries in a smart order to avoid repeatedly checking the same items?

How can we use the answer to a query for other queries?

Similar Questions: