Easiest Solution !! Beats 82% (Optimized)
Problem Analysis\nThe problem asks us to find the maximum beauty of an item that has a price less than or equal to a given query price. Each item is represented
# Problem Analysis\nThe problem asks us to find the maximum beauty of an item that has a price less than or equal to a given query price. Each item is represented as [price, beauty]. For each price in queries, we need to return the maximum beauty of items that have a price less than or equal to the query.\n# Intuition\n**1.** ***Sorting and Preprocessing:***\n\nIf we sort items by price, we can preprocess to find the maximum beauty seen so far for any given price.\n\nThis allows us to quickly determine the maximum beauty for any price limit using binary search.\n\n**2.** ***Efficient Querying:***\n\nOnce we preprocess the maximum beauty for increasing prices, we can use binary search to quickly answer each query.\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n**1.** ***Sort items by price:***\n\nSorting the items helps us to build a list of prices and corresponding maximum beauties in increasing order.\n\n**2.** ***Preprocess Maximum Beauty:***\n\nIterate through the sorted items and maintain the highest beauty encountered so far.\nStore each unique price and its corresponding maximum beauty in a list v (as a pair of (price, max_beauty)).\n\n**3.** ***Answer Queries Using Binary Search:***\n\nFor each query, use lower_bound (binary search) to find the maximum price that is less than or equal to the query price.\nIf such a price is found, return the associated maximum beauty; otherwise, return 0.\n<!-- Describe your approach to solving the problem. -->\n\n# Explanation of the Code\n**1.** ***Sorting Items:***\n\nSorting the items based on price allows us to efficiently find the maximum beauty up to any price.\n\n**2.** ***Building the Preprocessed List (v):***\n\nWe keep track of the maximum beauty encountered so far.\n\nWe only add a new entry if the price changes, ensuring the list remains compact.\n\n**3.** ***Binary Search for Each Query:***\n\nFor each query, use lower_bound to find the smallest element greater than query + 1.\n\nIf the iterator points to the beginning, it means there is no item with a price \u2264 query, so return 0.\n\nOtherwise, return the beauty of the largest item with a price \u2264 query.\n\n# Complexity\n- **Time complexity**: O(n log n + m log n)  *where m is the length of queries* \n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- **Space complexity:** O(n + m)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n![Screenshot 2024-11-12 115044.png](https://assets.leetcode.com/users/images/08c88669-c281-44ed-beff-170272ec5ef2_1731393661.558908.png)\n\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {\n        sort(items.begin(), items.end());\n\n        vector<pair<int, int>> v;\n        int maxBeauty = 0;\n\n        for (const auto& item : items) {\n            int price = item[0];\n            int beauty = item[1];\n            maxBeauty = max(maxBeauty, beauty);\n\n            if (v.empty() || v.back().first != price) {\n                v.push_back({price, maxBeauty});\n            }\n            if(v.back().first == price){\n                v.back().second = maxBeauty;\n            }\n        }\n\n        vector<int> ans;\n        for (int i = 0 ; i < queries.size() ; i++) {\n            auto it = lower_bound(v.begin(), v.end(), make_pair(queries[i]+1 , 0));\n            if (it == v.begin()) {\n                ans.push_back(0);\n            } else {\n                ans.push_back(prev(it)->second);\n            }\n        }\n\n        return ans;\n    }\n};\n\n```\n\n![Solution Image](https://assets.leetcode.com/users/images/d97c0243-2a44-4d9d-8c32-c81dc7384cac_1731393436.3782032.jpeg)\n\n\n\n
['Array', 'Binary Search', 'C', 'Sorting', 'C++']