Find Maximum Beauty within Budget 💸✨ | Efficient Solution for Query-Based Item Search 🕵️‍♀️
Intuition \uD83D\uDCA1\n\nTo find the most beautiful item within a budget for each query, we can leverage a sorted mapping of prices to their maximum achievable
# Intuition \uD83D\uDCA1\n\nTo find the most beautiful item within a budget for each query, we can leverage a sorted mapping of prices to their maximum achievable beauty. This allows us to quickly answer each query using binary search on price limits.\n\n---\n\n# Approach \uD83D\uDEE0\uFE0F\n\n1. **Build Maximum Beauty Map**:\n   - First, map each price to its highest possible beauty using a dictionary (`mp`).\n   - For each price in sorted order, we ensure that the beauty at a given price is at least the beauty of any lower-priced items.\n\n2. **Precompute Cumulative Maximums**:\n   - Convert the mapping into a list of keys (`keys`), where each position reflects cumulative maximum beauty up to that price.\n\n3. **Answer Each Query Efficiently**:\n   - For each query, use binary search (`upper_bound`) on `keys` to find the closest price less than or equal to the query budget. This enables quick access to the maximum achievable beauty within the budget.\n\n---\n\n# Complexity \u23F3\n\n- **Time Complexity**: $$O(n \\log n + m \\log n)$$, where $$n$$ is the number of items and $$m$$ is the number of queries.\n- **Space Complexity**: $$O(n)$$ for the `map` and `keys` array.\n\n---\n![c1ee5054-dd07-4caa-a7df-e21647cfae9e_1709942227.5165014.png](https://assets.leetcode.com/users/images/6d3894ad-c0e8-4267-803f-fd237581ab0d_1731387894.80231.png)\n\n\n# Code \uD83D\uDCBB\n\n```cpp\nclass Solution {\npublic:\n    vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {\n        // Step 1: Map each price to its maximum beauty\n        map<int, int> mp;\n        for (vector<int> item : items) {\n            mp[item[0]] = max(mp[item[0]], item[1]);\n        }\n\n        // Step 2: Precompute maximum beauty up to each price point\n        vector<int> keys(mp.size() + 1, 0);\n        int it = 1;\n        for (auto item : mp) {\n            keys[it] = item.first;\n            mp[keys[it]] = max(mp[keys[it]], mp[keys[it - 1]]);\n            it++;\n        }\n\n        // Step 3: Answer each query using binary search\n        vector<int> res(queries.size());\n        it = 0;\n        for (int q : queries) {\n            int i = upper_bound(keys.begin(), keys.end(), q) - keys.begin() - 1;\n            res[it] = mp[keys[i]];\n            it++;\n        }\n\n        return res;\n    }\n};\n```\n\n---\n\n# Explanation \uD83D\uDCD8\n\n1. **Mapping Price to Maximum Beauty**: This ensures that at any price point, we only consider the most beautiful item.\n2. **Binary Search for Fast Query Resolution**: Each query is resolved in $$O(\\log n)$$ time by finding the closest price within the budget using `upper_bound`.\n\n---\n\n> # Found this solution helpful? **Upvote and Share!** \uD83D\uDC4D\n\n![1HBC0324_COV.jpg](https://assets.leetcode.com/users/images/b76d2ded-5efe-438d-a49e-db08f0748c7a_1731387849.1212122.jpeg)\n
['Array', 'Binary Search', 'Sorting', 'C++']