🌟 Beats 100.00% 👏 || For loop || Explained with example
\n\n# Intuition\n Describe your first thoughts on how to solve this problem. \nThe goal of this algorithm is to find the maximum "beauty" of items a person can 
![image.png](https://assets.leetcode.com/users/images/144a4343-86b9-4de7-b862-3b7cdcd5c30e_1731377428.021342.png)\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe goal of this algorithm is to find the maximum "beauty" of items a person can afford, given an array of items, where each item is represented as [price, beauty], and an array of queries, where each query represents an available budget.\n\nTo do this efficiently:\n\nWe preprocess the items to build a "price-beauty bracket" where each entry stores the highest possible beauty value achievable up to a certain price.\nFor each query, we quickly look up the maximum beauty achievable within that budget by consulting our preprocessed data.\nThis allows us to answer each query in constant time after the preprocessing step.\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe algorithm is divided into two main parts: preprocessing the items and processing the queries.\n\nPart 1: Preprocessing\nSort the Items by Price: We first sort the items array by price in ascending order. Sorting helps ensure that each processed item has a price greater than or equal to previous items, allowing us to build a cumulative "price-beauty bracket."\n\nConstruct Price-Beauty Brackets:\n\nWe create a list res to store "price-beauty brackets." Each bracket is represented as [min_price, max_beauty, max_price].\nStarting with a bracket [0, 0, \u221E], which represents zero budget, we iterate over each item in sorted order:\nIf the current item\'s beauty is higher than the last recorded beauty in res, we add a new bracket with the current item\'s price and beauty, updating the last bracket\u2019s max_price to the current price.\nResult of Preprocessing: At the end of preprocessing, res will contain cumulative price-beauty brackets, allowing us to check the maximum beauty for any budget by examining the highest bracket we can afford.\n\nPart 2: Processing the Queries\nFor each budget in queries, we iterate backward through res (from the most expensive bracket to the least) and find the first bracket with a minimum price that fits within the query budget.\nWe record the corresponding beauty value in the result array.\n\n# Example\nSuppose we have:\n\nitems = [[1, 2], [3, 4], [5, 6], [6, 8]] (price-beauty pairs)\nqueries = [2, 3, 5, 7] (budgets)\nStep-by-Step Execution\nSorting Items by Price\n\nAfter sorting (already sorted here), we have items = [[1, 2], [3, 4], [5, 6], [6, 8]].\nBuilding the Price-Beauty Brackets (res)\n\nInitialize res with [0, 0, \u221E].\nProcess each item:\nItem [1, 2]: Since 2 > 0 (last bracket\'s beauty), add a new bracket [1, 2, \u221E] and set the last bracket\u2019s max_price to 1.\nItem [3, 4]: Since 4 > 2, add [3, 4, \u221E] and update the previous bracket\u2019s max_price to 3.\nItem [5, 6]: Since 6 > 4, add [5, 6, \u221E] and update the previous bracket\u2019s max_price to 5.\nItem [6, 8]: Since 8 > 6, add [6, 8, \u221E] and update the previous bracket\u2019s max_price to 6.\nFinal res: [[0, 0, 1], [1, 2, 3], [3, 4, 5], [5, 6, 6], [6, 8, \u221E]].\nAnswering Queries\n\nFor each query in queries, find the maximum beauty that can be afforded.\nQuery 2: Find the last bracket with min_price <= 2. Result: bracket [1, 2, 3], so beauty is 2.\nQuery 3: Last bracket with min_price <= 3. Result: bracket [3, 4, 5], so beauty is 4.\nQuery 5: Last bracket with min_price <= 5. Result: bracket [5, 6, 6], so beauty is 6.\nQuery 7: Last bracket with min_price <= 7. Result: bracket [6, 8, \u221E], so beauty is 8.\nOutput\nThe final output for the queries [2, 3, 5, 7] would be [2, 4, 6, 8].\n\n# Complexity\n- Time complexity:O(N log N)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(M)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```javascript []\nvar maximumBeauty = function (items, queries) {\n    const maxI = Number.MAX_SAFE_INTEGER;\n    let res = [[0, 0, maxI]]\n\n    items.sort((a, b) => a[0] - b[0])\n\n    for (let item of items) {\n        let price = item[0]\n        let beauty = item[1]\n        let lastBracket = res.at(-1)\n\n        if (beauty > lastBracket[1]) {\n            res[res.length - 1][2] = price\n            res.push([price, beauty, maxI])\n        }\n    }\n\n    let ans = []\n\n    for (let x of queries) {\n        for (let i = res.length - 1; i > -1; i--) {\n            if (res[i][0] <= x) {\n                ans.push(res[i][1])\n                break\n            }\n        }\n    }\n\n    return ans\n\n};\n```\n```python []\nclass Solution(object):\n    def maximumBeauty(self, items, queries):\n        \n        maxI = float(\'inf\')\n        res = [[0, 0, maxI]]\n    \n        items.sort(key=lambda x: x[0])\n\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\n        ans = []\n\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\n        return ans\n\n```\n```java []\nimport java.util.*;\n\npublic class Solution {\n    public int[] maximumBeauty(int[][] items, int[] queries) {\n        int maxI = Integer.MAX_VALUE;\n        List<int[]> res = new ArrayList<>();\n        res.add(new int[] {0, 0, maxI});\n\n        Arrays.sort(items, Comparator.comparingInt(a -> a[0]));\n\n        for (int[] item : items) {\n            int price = item[0];\n            int beauty = item[1];\n            int[] lastBracket = res.get(res.size() - 1);\n\n            if (beauty > lastBracket[1]) {\n                lastBracket[2] = price;\n                res.add(new int[] {price, beauty, maxI});\n            }\n        }\n\n        int[] ans = new int[queries.length];\n\n        for (int j = 0; j < queries.length; j++) {\n            int x = queries[j];\n            for (int i = res.size() - 1; i >= 0; i--) {\n                if (res.get(i)[0] <= x) {\n                    ans[j] = res.get(i)[1];\n                    break;\n                }\n            }\n        }\n\n        return ans;\n    }\n}\n\n```\n```c++ []\n#include <vector>\n#include <algorithm>\n#include <climits>\n\nusing namespace std;\n\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\n        sort(items.begin(), items.end());\n\n        for (const auto& item : items) {\n            int price = item[0];\n            int beauty = item[1];\n            if (beauty > res.back()[1]) {\n                res.back()[2] = price;\n                res.push_back({price, beauty, maxI});\n            }\n        }\n\n        vector<int> ans;\n\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\n        return ans;\n    }\n};\n```\n
['Array', 'Binary Search', 'C', 'Sorting', 'Python', 'C++', 'Java', 'Python3', 'JavaScript']