Python | 83ms | Beats 100% | Greedy
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem is about finding the maximum beauty for each given query where the price of
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem is about finding the maximum beauty for each given query where the price of the item is less than or equal to the query price. Given that both the items and queries can be very large, a brute force approach (checking each query against all items) would be inefficient. The goal is to use sorting and efficient look-up techniques to optimize the process.\n\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n**Sort Items:** \nStart by sorting the items based on their price. This allows us to efficiently process the maximum beauty up to any given price point.\n\n**Initialize Variables:**\n\nmaxB: To keep track of the maximum beauty encountered as we process each item. This value is updated whenever an item with higher beauty is found.\ni and j: Two pointers used to iterate through the queries and items, respectively.\n\n**Sort Queries:** \nSort the queries to align the processing of queries with the sorted items, enabling efficient computation of results.\n\n**Process Queries with Two Pointers:**\n\nUsing the two pointers (i for queries and j for items), iterate through the sorted queries.\nFor each query, check whether the current item\'s price is less than or equal to the query. If it is, update maxB (if the current item\'s beauty is greater than maxB), and move to the next item by incrementing j.\nIf the current item\'s price is greater than the query price or if all items have been processed, just move to the next query by incrementing i.\nStore the maximum beauty found for each query price in a dictionary.\n\n**Build Result:**\n After processing all queries, construct the output list using the dictionary values corresponding to the original queries. This step ensures that each query gets the correct maximum beauty value based on its original order, not the sorted order.\n\n# Complexity\n- Time complexity:$$O(Nlogn+Qlogq)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:$$O(n+q)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Sanitized Code\n```python3 []\nclass Solution:\n    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:\n        # Sort items based on their price in ascending order\n        items.sort(key=lambda x: x[0])\n        \n        # Dictionary to store the maximum beauty for each query\n        dict1 = {}\n        \n        # Variables to keep track of the maximum beauty, and indices for items and queries\n        max_beauty = 0\n        item_index = 0\n        query_index = 0\n        \n        # Sort the queries to process them in order\n        sorted_queries = sorted(queries)\n        \n        # Process each query\n        while query_index < len(sorted_queries):\n            current_query = sorted_queries[query_index]\n            \n            # Update the maximum beauty as long as there are items that can be bought within current_query price\n            while item_index < len(items) and current_query >= items[item_index][0]:\n                max_beauty = max(max_beauty, items[item_index][1])\n                item_index += 1\n            \n            # Store the maximum beauty for the current query price\n            dict1[current_query] = max_beauty\n            query_index += 1\n        \n        # Return the results for the original order of queries\n        return [dict1[query] for query in queries]\n```\n\n# Original Code\n\n```python3 []\nclass Solution:\n    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:\n        items.sort(key = lambda x: x[0])\n        dict1 = {}\n        maxB = i = j = 0\n        q= sorted(queries)\n        while i<len(q):\n            while j<len(items) and q[i]>=items[j][0]:\n                maxB = max(maxB, items[j][1] )\n                j+=1                \n            dict1[q[i]] = maxB\n            i+=1\n        return [dict1[i] for i in queries]\n```\n\n\n![image.png](https://assets.leetcode.com/users/images/9e0f2297-eb33-4a77-975f-d5bf622194e9_1731443716.7704554.png)\n\n
['Array', 'Sorting', 'Python3']