Optimal Approach to Maximum Beauty Queries Using Price Mapping and Binary Search | Python3
Intuition\nThe goal is to answer each query by finding the maximum beauty of items that have a price less than or equal to the query price. This involves both f
### Intuition\nThe goal is to answer each query by finding the maximum beauty of items that have a price less than or equal to the query price. This involves both finding the highest beauty value up to a certain price threshold and being able to efficiently retrieve this value for each query. \n\nTo achieve this, we can take advantage of sorting and use a binary search to quickly find the maximum beauty for prices that do not exactly match any given query. By sorting the items based on price and storing the cumulative maximum beauty for each price, we can ensure that we access the best possible beauty values without re-calculating for each query.\n\n### Approach\n1. **Sort Items by Price**: First, sort the `items` list in ascending order of price. This allows us to process items in increasing order, ensuring that each price has the maximum beauty recorded up to that point.\n\n2. **Create a Mapping of Price to Maximum Beauty**:\n   - Initialize a dictionary, `fmap`, to store each price along with the maximum beauty achievable at that price or any lower price.\n   - Iterate through the sorted `items` list. For each item, update `mx` to be the maximum beauty encountered so far, and map the current price to this maximum beauty in `fmap`.\n\n3. **Process Queries Using Binary Search**:\n   - For each query, check if the query price exists directly in `fmap`. If it does, retrieve the beauty value directly.\n   - If the query price does not exist in `fmap`, perform a binary search on the sorted list of `fmap` keys to find the largest price that is less than or equal to the query price. Use this price to retrieve the corresponding maximum beauty.\n   - Append the beauty value for each query to the `ans` list, returning `0` if no valid price was found.\n\n4. **Return Results**: After processing all queries, return the `ans` list containing the maximum beauty for each query price.\n\n### Complexity\n- **Time Complexity**:\n  - Sorting the `items` array takes \\(O(n \\log n)\\), where \\(n\\) is the number of items.\n  - Creating the `fmap` dictionary takes \\(O(n)\\), as we iterate through the sorted items.\n  - Each query requires \\(O(\\log n)\\) time for a binary search on `fmap` keys, and with \\(q\\) queries, this part takes \\(O(q \\log n)\\).\n  - Overall, the time complexity is \\(O((n + q) \\log n)\\).\n\n- **Space Complexity**:\n  - Storing the `fmap` dictionary requires \\(O(n)\\) space for the maximum beauties mapped to unique prices.\n  - The `ans` array requires \\(O(q)\\) space.\n  - Thus, the total space complexity is \\(O(n + q)\\).\n\n# Code\n```python3 []\nclass Solution:\n    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:\n        items.sort()\n        fmap = dict()\n        n = len(items)\n        mx = float(\'-inf\')\n        for lst in items:\n            mx = max(mx,lst[1])\n            fmap[lst[0]] = mx\n        ans = []\n        k = list(fmap.keys())\n        for ele in queries:\n            if ele in fmap:\n                ans.append(fmap[ele])\n            else:\n                l = 0\n                r = len(k)-1 \n                idx = -1\n                while l<=r:\n                    mid = (l+r)//2\n                    if k[mid]<ele:\n                        idx = mid\n                        l = mid+1\n                    else:\n                        r = mid-1\n                if idx!=-1:\n                    ans.append(fmap[k[l-1]])\n                else:\n                    ans.append(0)\n        return ans\n\n\n```
['Array', 'Binary Search', 'Sorting', 'Python3']