Python | Two-Pointer & Binary Search
see the Successfully Accepted Submission\n\n# Code\npython3 []\nclass Solution:\n    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List
[see the Successfully Accepted Submission](https://leetcode.com/problems/most-beautiful-item-for-each-query/submissions/1450113444/?envType=daily-question&envId=2024-11-12)\n\n# Code\n```python3 []\nclass Solution:\n    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:\n        # Sort items by price (first element in each sublist)\n        items.sort()\n        \n        # Precompute the maximum beauty at each price level\n        max_beauty_at_price = []\n        current_max_beauty = 0\n        \n        for price, beauty in items:\n            current_max_beauty = max(current_max_beauty, beauty)\n            max_beauty_at_price.append((price, current_max_beauty))\n        \n        # Sort queries with indices to map results back to original order\n        sorted_queries = sorted((q, i) for i, q in enumerate(queries))\n        \n        # Prepare result array\n        result = [0] * len(queries)\n        \n        # Process each query\n        for query, original_index in sorted_queries:\n            # Binary search to find the largest price <= query\n            idx = bisect_right(max_beauty_at_price, (query, float(\'inf\'))) - 1\n            if idx >= 0:\n                result[original_index] = max_beauty_at_price[idx][1]\n            else:\n                result[original_index] = 0\n        \n        return result\n\n```\n# Solution Approach\n\n### 1. Sort the Items by Price:\n- **Objective**: Sort `items` based on price in ascending order. If two items have the same price, the order doesn\'t matter, as we will take the maximum beauty at each price level.\n- **Benefit**: This sorting allows us to answer each query more efficiently by reducing the search space.\n\n### 2. Optimize Beauty Up to Each Price:\n- As we iterate through the sorted `items`, maintain the maximum beauty seen so far.\n- For each unique price level, store the maximum beauty up to that price. This lets us quickly reference the maximum beauty available for any price without recalculating.\n\n### 3. Binary Search for Each Query:\n- After sorting and creating a cumulative maximum beauty array, sort the `queries`.\n- For each query, use binary search to find the largest price that is less than or equal to the query price.\n- Use this position to get the precomputed maximum beauty for that price.\n\n### 4. Result Matching:\n- Since we sorted `queries`, we must match the results back to the original query order.\n\n# Time Complexity Analysis\n- Sorting `items` takes \\(O(N \\log N)\\).\n- Sorting `queries` also takes \\(O(Q \\log Q)\\).\n- Processing each query with a binary search on `items` takes \\(O(Q \\log N)\\).\n  \nOverall complexity: \\(O((N + Q) \\log N)\\), which is efficient within the given constraints.\n\n#Code Explanation:\nSorting items:\n\nSorting makes it easy to process prices in increasing order and maintain a cumulative maximum beauty.\nBuilding max_beauty_at_price:\n\nFor each item, update current_max_beauty if the beauty of the item is higher. Append (price, current_max_beauty) so we have each price level\'s max beauty.\nSorting and Processing queries:\n\nSorting queries avoids redundant computations and lets us easily pair results back to the original order.\nBinary Search:\n\nFor each query, use bisect_right to find the rightmost price that is \u2264 the query value, then access the corresponding max beauty from max_beauty_at_price.\n\n#Edge Cases\nNo items with price \u2264 query: The answer for that query should be 0.\nMultiple items with the same price: Handled by taking the maximum beauty at each price.\nAll queries are smaller than the minimum item price: All query results should be 0.\n\n\n![image](https://assets.leetcode.com/users/images/b1e4af48-4da1-486c-bc97-b11ae02febd0_1696186577.992237.jpeg)
['Python3']