Multiple Approaches Explained || Sorting , Binary Search & Offline Query  || C++ Clean Code
-----------------------------------------------------\n# Approach 1: Sorting + Binary Search\n-----------------------------------------------------\n\n---------
-----------------------------------------------------\n# **Approach 1: Sorting + Binary Search**\n-----------------------------------------------------\n\n-----------------------------------------------------\n * **Code :**\n\n\t\tvector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {\n\n\t\t\tint n = items.size();\n\n\t\t\tsort(items.begin(), items.end());\n\n\t\t\tvector<int> maxBeautyTillNow(n, 0);\n\n\t\t\tfor(int i=0; i<n; i++) {\n\t\t\t\tmaxBeautyTillNow[i] = (i == 0) ? items[i][1] : max(maxBeautyTillNow[i-1], items[i][1]);\n\t\t\t}\n\n\t\t\tvector<int> answer;\n\t\t\tfor(auto& query : queries) {\n\t\t\t\tint idx = upper_bound(items.begin(), items.end(), vector<int>({query, INT_MAX})) - items.begin();\n\n\t\t\t\tif(idx >= n || items[idx][0] > query) idx--;\n\n\t\t\t\tif(idx < 0) answer.push_back(0);\n\t\t\t\telse answer.push_back(maxBeautyTillNow[idx]);\n\t\t\t}\n\n\t\t\treturn answer;\n\t\t}\n\n-----------------------------------------------------\n\n* **Complexity :**\n\n\t* Time : `O(N logN) + O(N) + O(Q logN)` \n\t\t* `O(N logN)` : sorting `items` list, \n\t\t* `O(N)` : building prefix max i.e `maxBeautyTillNow` array and \n\t\t* `O(Q logN)` : searching index for each query in `queries`\n\n\n\t* Space : `O(N)`, N is size of `items` list\n\t\t* N : Size of `items` list\n\t\t* Q : Size of `queries` list\n-----------------------------------------------------\n-----------------------------------------------------\n# **Approach 2 : Sorting + Offline Query**\n-----------------------------------------------------\n\n-----------------------------------------------------\n * **Code :**\n\n\t\tvector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {\n\n\t\t\tint n = items.size();\n\t\t\tint m = queries.size();\n\n\t\t\tsort(begin(items), end(items));\n\n\t\t\tvector<pair<int, int>> newQueries;\n\t\t\tint i=0; \n\t\t\tfor(auto& q : queries) {\n\t\t\t\tnewQueries.push_back({q, i++});\n\t\t\t}\n\n\t\t\tsort(begin(newQueries), end(newQueries));\n\n\t\t\tint idx = 0, maxBeauty = 0;\n\t\t\tvector<int> answer(m, 0);\n\n\t\t\tfor(auto& [query, index] : newQueries) {\n\n\t\t\t\twhile(idx < n && items[idx][0] <= query) {\n\t\t\t\t\tmaxBeauty = max(maxBeauty, items[idx][1]);\n\t\t\t\t\tidx++;\n\t\t\t\t}\n\n\t\t\t\tanswer[index] = maxBeauty;\n\t\t\t}\n\n\t\t\treturn answer;\n\t\t}\n-----------------------------------------------------\n\n* **Complexity :**\n\n\t* Time : `O(N logN) + O(Q + Q log Q) + O(Q + N)` \n\t\t* `O(N log N)` : sorting `items` list, \n\t\t* `O(Q + Q logQ )` : creating and sorting `newQueries` list, \n\t\t* `O(Q + N)` : processing query in `newQueries`\n\n\t* Space : `O(Q)`, Q is size of `queries` list\n\t\t* N : Size of `items` list\n\t\t* Q : Size of `queries` list\n-----------------------------------------------------\n\n***If you find this helpful, do give it a like :)***
['C', 'Sorting', 'Binary Tree']