(Beat 55%) Easy Approach & Easy to understand 😊😊
Intuition\n Describe your first thoughts on how to solve this problem. \nThe code uses sorting and a prefix maximum transformation to efficiently answer each qu
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe code uses sorting and a prefix maximum transformation to efficiently answer each query with binary search. By preprocessing items so that each entry stores the highest achievable beauty up to that price, the binarySearch can quickly find the maximum beauty value for any given target price.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Sort items: The items array is sorted by price in ascending order. This allows us to efficiently find items priced up to a certain value, using binary search later on.\n\n2. Optimize beauty values: As we iterate through the sorted items, we maintain the maximum beauty encountered so far. This allows us to update each item\u2019s beauty value to be the maximum beauty for all items with a price up to that item\u2019s price. This transformation prepares the data so that for any price point, the maximum beauty value up to that price is already computed.\n\n3. Binary search on queries: For each query, the binary search function (binarySearch) helps us find the maximum beauty for items priced up to the query\u2019s target price.\n\n- The binary search finds the highest index in items such that items[mid][0] <= target price.\n- If an item meets this criterion, the corresponding beauty is returned. Otherwise, if no such item is found, we return 0 since no item meets the target price.\n\n# Complexity\n- Time complexity: the overall complexity is \uD835\uDC42((\uD835\uDC5B+\uD835\uDC5A)log \uD835\uDC5B).\n\n# Code\n```java []\nclass Solution {\n    public int[] maximumBeauty(int[][] items, int[] queries) {\n        int len = queries.length;\n        int val = Integer.MIN_VALUE;\n        Arrays.sort(items,Comparator.comparingInt(a -> a[0]));\n        for(int i = 0;i < items.length;i++){\n            val = Math.max(val,items[i][1]);\n            items[i][1] = val;\n        }\n        for(int i = 0;i < len;i++){\n            queries[i] = binarySearch(items,queries[i]);\n        }\n        return queries;\n    }\n    public int binarySearch(int[][] items, int tar){\n        int end = items.length-1;\n        int start = 0;\n        while(start <= end){\n            int mid = start+((end-start)/2);\n            if(items[mid][0] <= tar){\n                start = mid+1;\n            }\n            else{\n                end = mid-1;\n            }\n        }\n        return start-1 == -1 ? 0 : items[start-1][1];\n    }\n}\n```
['Binary Search', 'Sorting', 'Java']