JAVA || EASY TO UNDERSTAND || BEATS 92%  🚀 || O(nlogn)
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem is essentially to find, for each query price, the maximum beauty of items t
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem is essentially to find, for each query price, the maximum beauty of items that have a price less than or equal to that query price. This suggests a combination of sorting and binary search:\n1. **Sorting** helps organize items by price, making it easier to find the maximum beauty for any given price threshold.\n2. **Binary Search** allows efficient searching within this sorted list for each query price.\n\nBy sorting the items by price and then using binary search for each query, we can efficiently determine the maximum beauty available under or equal to each query price.\n\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. **Sort the Items by Price**:\n   - First, sort `items` based on their price in ascending order. This ensures that for any price threshold, the items we need to consider are sequentially arranged.\n\n2. **Process Each Query Using Binary Search**:\n   - For each query, we perform a binary search on the sorted `items` array.\n   - The goal is to find the largest price in `items` that is less than or equal to the current query price.\n   - **Binary Search Steps**:\n     - Initialize `low` and `high` pointers.\n     - Calculate the middle point `mid` and check if `items[mid][0] <= queryPrice`.\n     - If yes, update `maxBeauty` to be the maximum of `maxBeauty` and `items[mid][1]`, and continue searching in the right half (`low = mid + 1`).\n     - If not, search in the left half (`high = mid - 1`).\n   - After the binary search completes, `maxBeauty` will hold the maximum beauty for the current query, and we update `queries[i]` directly.\n\n3. **Return the Updated `queries` Array**:\n   - The function modifies the `queries` array in place to store the maximum beauty for each query price, and this modified array is returned as the final result.\n\n# Complexity\n- **Time complexity:**\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n1. **Sorting** the `items` array takes \\(O(m \\log m)\\), where \\(m\\) is the number of items.\n2. **Binary Search** for each query takes \\(O(\\log m)\\), and since we have \\(n\\) queries, this part contributes \\(O(n \\log m)\\).\n\nOverall, the time complexity is: \\[O(m \\log m + n \\log m)\\]\nwhere:\n- \\(m\\) is the number of items.\n- \\(n\\) is the number of queries.\n\n- **Space complexity:** The space complexity is \\(O(1)\\) if we ignore the input and output storage, as the algorithm modifies `queries` in place without needing extra space for intermediate results.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n\n# Code\n```java []\nclass Solution {\n    public int[] maximumBeauty(int[][] items, int[] queries) {\n        Arrays.sort(items, (a,b) -> a[0]-b[0]);\n\n        for (int i = 1; i < items.length; i++) {\n            items[i][1] = Math.max(items[i][1], items[i - 1][1]);\n        }\n\n        for (int i = 0; i < queries.length; i++) {\n            int queryPrice = queries[i];\n            int low = 0, high = items.length - 1;\n            int maxBeauty = 0;\n\n            // Binary search for the highest price <= queryPrice\n            while (low <= high) {\n                int mid = low + (high - low) / 2;\n                if (items[mid][0] <= queryPrice) {\n                    maxBeauty = items[mid][1];\n                    low = mid + 1;\n                } else {\n                    high = mid - 1;\n                }\n            }\n            // Update queries[i] with the maximum beauty found\n            queries[i] = maxBeauty;\n        }\n        return queries;\n    }\n}\n```
['Array', 'Binary Search', 'Sorting', 'Java']