Thinking Process behind Binary Search and Sort with Pictures,  C++ implementation
Thinking Process\nYou must have seen many different solution in the discussion tab, everyone is saying that Sort + Binary Search!. But wait, from where did that
# Thinking Process\nYou must have seen many different solution in the discussion tab, everyone is saying that **Sort + Binary Search!**. But wait, from where did that even came from?\nLet me explain it to you in depth the thinking process behind this approach.\n\n* I am hoping that you know how to solve this with brute force approach. Let\'s start with something new.\n* The problem want us to find the maximum beauty out of all items for each query such that the price of each item is `<= query` itself.\n* So that\'s mean, the answer for query `q = 5` depends on items whose price is `<= 5`. ***And this also implies that we don\'t give a shit about items whose price value is greater than the query***. when you get this thought you probably got the idea of sorting.\n* With sorting we can optimise the brute force by avoiding unnecessary iterations over items.\n* But again, in worst case we might end up having the same time complexity as of brute force. So that\'s mean sorting alone is not enough.\n* Now let\'s write the items in sorted order first, than think of how to optimise it. I am using pen and paper, you can use whatever you like.\n\n![image](https://assets.leetcode.com/users/images/3b3c549e-5178-4536-9393-b83724372d23_1636821270.5248866.jpeg)\n\n* Now, in the image I have shared above only one thing you may found new that is the rectangular box I have made. It is nothing but the maximum beauty available till the current index in the available items. \n* Let\'s say we are looking for maximum beauty for query `q = 3`. You can easily see that the answer for this is` 7`. \n* If you closely look to the sorted array of items, you will realize that if you have that rectangular box with you than you just need the last index of query in the list of sorted items. If you have that you can easily find the maximum beauty for the current query in constant time. \n* And also finding the last index of an item in a sorted array is a standard binary search problem. ***That\'s is how we finally reach to Sorting + Binary Search solution.***\n\nSo, the answer for the queries shown in image is : [2, 2, 7, 7, 7, 7]. And yes don\'t forget to handle the edge case when the query do not exists in the items array.\n\n# C++ Implementation\n```\nclass Solution {\npublic:\n    int findLastIndex(vector<vector<int>>& items, int& q) {\n        // as usual binary search\n        int lo = 0, hi = items.size()-1, res = -1;\n        while(lo <= hi) {\n            int mid = lo+(hi-lo)/2;\n            \n            // if the current item price <= required item price\n            // than this might be our answer, so update answer \n            // and look for the right half for higher values\n            if(items[mid][0] <= q) {\n                res = mid;\n                lo = mid+1;\n            }\n            \n            // else we need to search in lower half\n            else {\n                hi = mid-1;\n            }\n        }\n        return res;\n    }\n    vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {\n        int n = items.size();\n        \n        // sort on the basis of first price\n        sort(begin(items), end(items));\n        \n        // maxBeauty store the max beauty till the current index, \n        // it will always be in increasing order\n        vector<int> maxBeauty(n);\n        vector<int> res;\n        \n        // assign the maximum beauty to each index\n        maxBeauty[0] = items[0][1];\n        for(int i=1; i<n; i++) {\n            maxBeauty[i] = max(maxBeauty[i-1], items[i][1]);\n        }\n        \n        // now for every query binary seach the last index in the pairs\n        // whose price <= current query price\n        for(auto q: queries) {\n            auto i = findLastIndex(items, q);\n                    \n            // if we do not find this item in the items list\n            res.push_back(i == -1 ? 0 : maxBeauty[i]);\n        }\n        \n        return res;\n    }\n};\n```\n\n# Time Complexity\n* I leave this to you, let me know in the comments. \n* Thanks for reading and Happy coding!.\n
[]