🌟 Beats 75.41 % 👏  ||  Easy and Step-by-Step Breakdown 🔥💯
\n\n## \uD83C\uDF1F Access Daily LeetCode Solutions Repo : click here\n\n---\n\n\n\n---\n\n# Intuition\nWhen I first looked at this problem, I noticed that we n
![github_promotion_dark.png](https://assets.leetcode.com/users/images/bbf62b19-eebe-4c05-9ddc-d3782ab20f8f_1731377469.8498797.png)\n\n## **\uD83C\uDF1F Access Daily LeetCode Solutions Repo :** [click here](https://github.com/withaarzoo/LeetCode-Solutions)\n\n---\n\n![image.png](https://assets.leetcode.com/users/images/e1dde3a2-2944-4ec9-8a87-ef1f39b1c70c_1731377311.5075152.png)\n\n---\n\n# Intuition\nWhen I first looked at this problem, I noticed that we needed to answer multiple queries by finding the "most beautiful" item within a certain price range for each query. This means we need to efficiently compare items and quickly determine the maximum beauty within each price range. My initial thought was that sorting the items by price and precomputing maximum beauty values would allow us to answer each query in constant time.\n\nBy keeping a running maximum of beauty values for each unique price, we can use binary search on the sorted list to find the maximum beauty for any price constraint given in the queries.\n\n---\n\n# Approach\nHere\'s a breakdown of my approach:\n\n1. **Sort the Items by Price**: I sorted the items by price to ensure that we can easily find items with prices less than or equal to any given query.\n\n2. **Create a Running Maximum of Beauty Values**: As I iterate through the sorted items, I keep track of the maximum beauty seen so far and store it alongside each price. This allows us to know the highest beauty achievable for any price range.\n\n3. **Binary Search for Each Query**: For each query, I used binary search to find the largest price that does not exceed the query price. Using this position, I could quickly get the maximum beauty value for that price. If no such price exists, we return 0.\n\nThis approach combines sorting and binary search to ensure efficient processing of both the items and the queries.\n\n---\n\n# Complexity\n- **Time complexity**: Sorting the items takes \\(O(N \\log N)\\), where \\(N\\) is the number of items. Each query takes \\(O(\\log N)\\) to binary search through the sorted list, making the total complexity \\(O(N \\log N + Q \\log N)\\), where \\(Q\\) is the number of queries.\n- **Space complexity**: We use \\(O(N)\\) space for storing the precomputed prices and beauty values.\n\n---\n\n# Code\n```C++ []\n#include <vector>\n#include <algorithm>\nusing namespace std;\n\nclass Solution {\npublic:\n    vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {\n        // Sort items by price\n        sort(items.begin(), items.end());\n\n        // Prepare price-beauty pairs with running max beauty\n        vector<pair<int, int>> priceBeauty;\n        int maxBeauty = 0;\n        for (auto& item : items) {\n            maxBeauty = max(maxBeauty, item[1]);\n            priceBeauty.push_back({item[0], maxBeauty});\n        }\n\n        // Process each query\n        vector<int> result;\n        for (int query : queries) {\n            auto it = upper_bound(priceBeauty.begin(), priceBeauty.end(), make_pair(query, INT_MAX)) - 1;\n            result.push_back(it >= priceBeauty.begin() ? it->second : 0);\n        }\n        return result;\n    }\n};\n\n```\n```Java []\nimport java.util.*;\n\nclass Solution {\n    public int[] maximumBeauty(int[][] items, int[] queries) {\n        Arrays.sort(items, Comparator.comparingInt(a -> a[0]));\n\n        List<int[]> priceBeauty = new ArrayList<>();\n        int maxBeauty = 0;\n        for (int[] item : items) {\n            maxBeauty = Math.max(maxBeauty, item[1]);\n            priceBeauty.add(new int[]{item[0], maxBeauty});\n        }\n\n        int[] result = new int[queries.length];\n        for (int i = 0; i < queries.length; i++) {\n            int query = queries[i];\n            int idx = binarySearch(priceBeauty, query);\n            result[i] = idx != -1 ? priceBeauty.get(idx)[1] : 0;\n        }\n        return result;\n    }\n\n    private int binarySearch(List<int[]> priceBeauty, int query) {\n        int left = 0, right = priceBeauty.size() - 1;\n        while (left <= right) {\n            int mid = left + (right - left) / 2;\n            if (priceBeauty.get(mid)[0] <= query) left = mid + 1;\n            else right = mid - 1;\n        }\n        return right;\n    }\n}\n\n```\n```JavaScript []\n/**\n * @param {number[][]} items\n * @param {number[]} queries\n * @return {number[]}\n */\nvar maximumBeauty = function(items, queries) {\n    items.sort((a, b) => a[0] - b[0]);\n    let priceBeauty = [];\n    let maxBeauty = 0;\n\n    for (let [price, beauty] of items) {\n        maxBeauty = Math.max(maxBeauty, beauty);\n        priceBeauty.push([price, maxBeauty]);\n    }\n\n    return queries.map(query => {\n        let left = 0, right = priceBeauty.length - 1;\n        while (left <= right) {\n            let mid = left + Math.floor((right - left) / 2);\n            if (priceBeauty[mid][0] <= query) left = mid + 1;\n            else right = mid - 1;\n        }\n        return right >= 0 ? priceBeauty[right][1] : 0;\n    });\n};\n\n```\n```Python []\nfrom bisect import bisect_right\nfrom typing import List\n\nclass Solution:\n    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:\n        items.sort()\n        price_beauty = []\n        max_beauty = 0\n\n        for price, beauty in items:\n            max_beauty = max(max_beauty, beauty)\n            price_beauty.append((price, max_beauty))\n\n        result = []\n        for query in queries:\n            idx = bisect_right(price_beauty, (query, float(\'inf\'))) - 1\n            result.append(price_beauty[idx][1] if idx >= 0 else 0)\n        \n        return result\n\n```\n```Go []\nimport (\n    "sort"\n)\n\nfunc maximumBeauty(items [][]int, queries []int) []int {\n    sort.Slice(items, func(i, j int) bool {\n        return items[i][0] < items[j][0]\n    })\n\n    priceBeauty := make([][2]int, 0)\n    maxBeauty := 0\n    for _, item := range items {\n        price, beauty := item[0], item[1]\n        maxBeauty = max(maxBeauty, beauty)\n        priceBeauty = append(priceBeauty, [2]int{price, maxBeauty})\n    }\n\n    result := make([]int, len(queries))\n    for i, query := range queries {\n        idx := sort.Search(len(priceBeauty), func(j int) bool {\n            return priceBeauty[j][0] > query\n        }) - 1\n        if idx >= 0 {\n            result[i] = priceBeauty[idx][1]\n        } else {\n            result[i] = 0\n        }\n    }\n    return result\n}\n\nfunc max(a, b int) int {\n    if a > b {\n        return a\n    }\n    return b\n}\n\n```\n\n---\n\n# Step-by-Step Detailed Explanation\n\n1. **Sort the Items**: We first sort the items by price. This allows us to maintain an increasing sequence of prices, making it easier to find items that fall within any price range.\n\n2. **Compute Running Maximum Beauty**: By iterating over the sorted items and keeping track of the maximum beauty encountered so far, we create a list of pairs `[price, maxBeauty]`. For each price, we store the highest beauty achievable at or below that price.\n\n3. **Binary Search on Queries**: For each query, we perform a binary search on the `priceBeauty` list to find the highest price that does not exceed the query price. Using this index, we can directly retrieve the maximum beauty for that price range.\n\nThis approach ensures that each query is handled efficiently by leveraging sorting and binary search. It\u2019s a practical and optimized solution to handle large inputs.\n\n---\n\n![upvote_cat.png](https://assets.leetcode.com/users/images/94f3aba2-a705-4ed9-aed6-0f7faf5764ed_1731377513.4401045.png)\n
['Array', 'Binary Search', 'Sorting', 'C++', 'Java', 'Go', 'Python3', 'JavaScript']