[C++] Sorting Queries | Explanation | Concise Code + Comments
Idea\nThe idea is to process the queries in the increasing order. I construct a 2D queries array of dimentions q * 2 which has the index of the query as the sec
**Idea**\nThe idea is to process the queries in the increasing order. I construct a 2D queries array of dimentions *q * 2* which has the index of the query as the second element of each query. This array is sorted on the basis of the first element i.e *the actual query value not its index*. The items array is sorted on the basis of price. Then the queries are processed in increasing order and using a *two-pointer approach*, I maintain an iterator which traverses items in increasing order and it points to the first item whose price is greater than the current query. While doing so, I also determine the maximum beauty encountered. This is the answer for the present query. \n\n**C++**\n```\nclass Solution {\npublic:\n    vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& qry) {\n        int n = items.size();\n        int q = qry.size();\n        vector<int> op(q);\n\t\t\n\t\t// Creating a 2D queries array to maintain the orginal indices of queries after sorting\n        vector<vector<int>> queries(q, vector<int>(2));\n        for(int i = 0; i < q; i++) {\n            queries[i] = {qry[i], i};\n        }\n        sort(queries.begin(), queries.end());\n        sort(items.begin(), items.end());\n        \n        int j = 0;\n        int ans = 0;\n\t\t\n\t\t// Traversing the queries in increasing order\n        for(int i = 0; i < q; i++) {\n\t\t\n\t\t\t// Finding the first item whose price is greater than the query\n\t\t\t// The maximum beauty encountered before this element \n\t\t\t// is the answer for the present query\n            while(j < n && items[j][0] <= queries[i][0]) {\n                ans = max(ans, items[j][1]);\n                j++;\n            }\n            op[queries[i][1]] = ans;\n        }\n        \n        return op;\n    }\n};\n```\n\n**Complexity Analysis**\n*Space Complexity (Auxiliary): O(q), where q is the number of queries.*\n*Time Complexity: O(nlogn + qlogq)*
[]