Beats 100 || C++ || Java || Python || with explanation🔥🔥
Intuition\nThe key idea behind this solution is to precompute the maximum beauty for each price. This allows us to quickly answer the queries without having to 
# Intuition\nThe key idea behind this solution is to precompute the maximum beauty for each price. This allows us to quickly answer the queries without having to search through all the items every time.\n\nBy sorting the items, we can ensure that the maximum beauty for a given price is the maximum beauty of all items with a price less than or equal to that price. This allows us to efficiently build the maxBeauty vector.\n\nOnce we have the maxBeauty vector, we can simply look up the maximum beauty for each query, which takes constant time.\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nSorting the items: We start by sorting the items vector based on the price of the items in ascending order. This will help us efficiently find the maximum beauty for each price.\n\nPrecomputing the maximum beauty: We then iterate through the sorted items and keep track of the maximum beauty seen so far. We store this maximum beauty for each price in a maxBeauty vector.\n\nAnswering the queries: For each query in queries, we need to find the maximum beauty of the items whose price is less than or equal to the current query. To do this, we use the maxBeauty vector to efficiently look up the maximum beauty for each query.\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {  \npublic:  \n    vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {  \n        int maxi = INT_MAX;  \n        vector<vector<int>> res = {{0, 0, maxi}};  \n        sort(items.begin(), items.end(), [](const vector<int>& a, const vector<int>& b) {  \n            return a[0] < b[0];  \n        });  \n        for (const auto& item : items) {  \n            auto& lastBracket = res.back();  \n            if (item[1] > lastBracket[1]) {  \n                lastBracket[2] = item[0];  \n                res.push_back({item[0], item[1], maxi});  \n            }  \n        }  \n        vector<int> ans;  \n        for (int x : queries) {  \n            for (int i = res.size() - 1; i >= 0; i--) {  \n                if (res[i][0] <= x) {  \n                    ans.push_back(res[i][1]);  \n                    break;  \n                }  \n            }  \n        }  \n        return ans;  \n    }  \n};\n\n```\n```python []\nclass Solution:\n    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:\n        maxi = float(\'inf\')\n        res = [[0,0,maxi]]\n        items.sort(key=lambda x: x[0])\n        for price,beauty in items:\n            lastbracket = res[-1]\n            if beauty > lastbracket[1]:\n                res[-1][2] = price\n                res.append([price,beauty,maxi])\n        ans = []\n        for x in queries:\n            for i in range(len(res)-1,-1,-1):\n                if res[i][0] <= x:\n                    ans.append(res[i][1])\n                    break\n        return\n```\n```Java []\nclass Solution {  \n    public int[] maximumBeauty(int[][] items, int[] queries) {  \n        // Sort the items based on price in ascending order  \n        Arrays.sort(items, (a, b) -> a[0] - b[0]);  \n\n        // Precompute the maximum beauty for each price  \n        int[] maxBeauty = new int[1000001];  \n        int maxSoFar = 0;  \n        for (int[] item : items) {  \n            maxSoFar = Math.max(maxSoFar, item[1]);  \n            maxBeauty[item[0]] = maxSoFar;  \n        }  \n\n        // Compute the answer for each query  \n        int[] answer = new int[queries.length];  \n        for (int i = 0; i < queries.length; i++) {  \n            int query = queries[i];  \n            int idx = findUpperBound(items, query);  \n            if (idx == 0) {  \n                answer[i] = 0;  \n            } else {  \n                answer[i] = maxBeauty[items[idx - 1][0]];  \n            }  \n        }  \n\n        return answer;  \n    }  \n\n    private int findUpperBound(int[][] items, int target) {  \n        int left = 0;  \n        int right = items.length - 1;  \n        while (left <= right) {  \n            int mid = left + (right - left) / 2;  \n            if (items[mid][0] <= target) {  \n                left = mid + 1;  \n            } else {  \n                right = mid - 1;  \n            }  \n        }  \n        return left;  \n    }  \n}\n```\n
['C++']