Easy & Simple Approach --> Most Beautiful Item for Each Query ✅ || Beats 100 % 🔥
Intuition\n Describe your first thoughts on how to solve this problem. \nThe goal is to find the maximum beauty of an item for each query, such that the item\'s
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe goal is to find the maximum beauty of an item for each query, such that the item\'s price is less than or equal to the query value. Given that each query should ideally search among items priced within a certain range, we can make this process efficient by sorting both items and queries. This allows us to process items in increasing order of price and answer queries in increasing order of their values, minimizing redundant checks.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1.\tSort Items by Price: We first sort items based on their prices. This helps us easily find items within any given query\'s price limit without having to repeatedly look through all items.\n2.\tSort Queries with Original Indices: Since we need to return results in the original order of queries, we store each query alongside its index, then sort the queries by their values. Sorting queries allows us to answer them efficiently by working from the lowest query value to the highest.\n3.\tIterate Through Items and Track Max Beauty:\n\u2022\tInitialize maxBeauty to keep track of the maximum beauty seen so far.\n\u2022\tFor each query in sorted order, check items that are affordable (i.e., items with prices <= current query).\n\u2022\tFor each affordable item, update maxBeauty if that item\u2019s beauty is higher than maxBeauty.\n4.\tAnswer Each Query:\n\u2022\tFor each query, after processing all affordable items, set the maxBeauty value for that query.\n\u2022\tStore the result for each query in ans, indexed by the original position of the query.\n5.\t  Return Result: After processing all queries, ans contains the maximum beauty values for each query in their original order.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n    O(NlogN+QlogQ), sorting items by price takes + sorting the queries by their values\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n    O(Q), Q is elements\n# Code\n```cpp []\nclass Solution {\npublic:\n    vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {\n        sort(items.begin(), items.end());\n        vector<pair<int, int>> queryIndex; // {query, index} \n        int n = queries.size();\n        //Store the queries with indices\n        for(int i = 0; i < n; i++)\n        {\n            queryIndex.push_back({queries[i], i});\n        }\n        sort(queryIndex.begin(), queryIndex.end());\n        vector<int> ans(n, 0);\n        int maxBeauty = 0;\n        int i = 0;\n        int m = items.size();\n        //To check out every items price as compare to the queries\n        for(auto& [query, index] : queryIndex)\n        {\n            while(i < m && items[i][0] <= query)\n            {\n                maxBeauty = max(maxBeauty, items[i][1]);\n                i++;\n            }\n            ans[index] = maxBeauty; // Store the max beauty for this query\n        }\n        return ans;\n    }\n};\n```\n```Java []\nclass Solution {\n    public int[] maximumBeauty(int[][] items, int[] queries) {\n        Arrays.sort(items, Comparator.comparingInt(a -> a[0]));\n\n        // Step 2: Sort queries with their original indices\n        int[][] queriesWithIndex = new int[queries.length][2];\n        for (int i = 0; i < queries.length; i++) {\n            queriesWithIndex[i][0] = queries[i];\n            queriesWithIndex[i][1] = i;\n        }\n        Arrays.sort(queriesWithIndex, Comparator.comparingInt(a -> a[0]));\n\n        int[] result = new int[queries.length];\n        int maxBeauty = 0;\n        int i = 0;\n\n        for (int[] queryWithIndex : queriesWithIndex) {\n            int query = queryWithIndex[0];\n            int index = queryWithIndex[1];\n\n            // Move through items that are within the current query\'s price range\n            while (i < items.length && items[i][0] <= query) {\n                maxBeauty = Math.max(maxBeauty, items[i][1]);\n                i++;\n            }\n\n            // Store the max beauty for this query\n            result[index] = maxBeauty;\n        }\n        return result;\n    }\n}\n```\n![upvote.jpeg.jpg](https://assets.leetcode.com/users/images/21a42fe8-c56d-49ac-ad88-6cef6ff0fd3a_1731387741.319845.jpeg)\n\n
['Binary Search', 'Sorting', 'C++', 'Java']