Greedy | Binary Search | Monotonic Stack O(nlogn) Time Complexity
Intuition\n- Here\'s the intuition behind the problem, although it\'s heavy implementation and we can learn a lot more concepts which opens our brain.\n- Now, w
# Intuition\n- Here\'s the intuition behind the problem, although it\'s heavy implementation and we can learn a lot more concepts which opens our brain.\n- Now, what we need?\n- we need to find the max sum of nums1[i]+nums2[i] such that nums1[i] >= x and nums2[i] >= y where (x,y) are queries.\n- Now, we can break down the problem, **we will find all the pairs which have nums1[i] >= x then in those pairs we can find nums2[i] >= y and among all those we have to find max sum**.\n- Firstly we need to find all those pairs which are **nums1[i] >= x**, now to avoid processing queries again and again.\n- **we can sort the queries and pairs{nums1[i],nums2[i]} in descending order**.\n- Why?\n- becoz to avoid furthur computations becoz for ex: if we perform for >= 3 in next iteration if we need >= 1 we don\'t need >= 3 right becoz it is previously performed.\n- **2 pointer approach is used to traverse**\n- Now, we get the all the pairs which satisfy **nums1[i] >= x**, now we maintain a **stack to store {nums2[i],nums1[i]+nums2[i]}.**\n- why? becoz we have already dealt with **x** now we need **y and sum**.\n- Now we maintain a **monotonic stack** why?\n- it is explained in code in detailed refer that.\n- now after getting the stack organised.\n- We can just get the just greater or equal pair **using lower bound**.\n- Now store the result in corresponding index.\n\n# Complexity\n- Time complexity: $$O(nlogn)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    void update(vector<pair<int,int>> &stack, int val, int sum) {\n        //what are we doing here.\n        //see if we have query as y = 2 and in our vector we have (3,4),(5,9)\n        //which one would you consider?\n        //obviously the one with max sum (5,9) then what is the use of (3,4)?\n        //for all y <= 5 the result is still (5,9)\n        //so discard all the sum which have less than current sum(assuming previously all pairs are \n        //already in monotonicity)\n        while(!stack.empty() && stack.back().second <= sum) {\n            stack.pop_back();\n        }\n        //if want to add the current pair to stack\n        //now think of it like this stack has top as (4,9) we have (3,5)\n        //anyway all the sums in stacks are removed the so the stack top sum is strictly \n        //greater than current sum\n        //now sum is greater now we want to add a lesser y value\n        //same case if we have query y = 2 then if we add (3,5) we will get (3,5) as result\n        //so to avoid that we won\'t add if (y < stack.top y value)\n        //then we can get (4,9)\n        if(!stack.empty() && val <= stack.back().first) return;\n        stack.push_back({val,sum});\n        //finally the stack should be of the form {(1,2),(4,5),(7,9)}\n        //both y and sum should be increasing fashion\n    }\n    vector<int> maximumSumQueries(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {\n        vector<pair<int,int>> pairs;\n        //form pairs\n        int n = nums1.size();\n        for(int i = 0;i < n;i++) {\n            pairs.push_back({nums1[i],nums2[i]});\n        }\n        //attach indices to queries for not loosing track of res when sorted\n        int i = 0;\n        for(auto &x : queries) {\n            x.push_back(i);\n            i++;\n        }\n        //sort pairs and queries in decreasing order\n        sort(pairs.begin(),pairs.end(),greater<pair<int,int>>());\n        sort(queries.begin(),queries.end(),greater<vector<int>> ());\n        //real stack is not used because we can\'t use lower bound for it \n        //so we use vector\n        vector<pair<int,int>> stack;\n        i = 0;\n        vector<int> res(queries.size(),-1);\n        for(auto &q : queries) {\n            int x = q[0];\n            int y = q[1];\n            int res_ind = q[2];\n            //now we only consider pairs which have nums1[i] >= x of query\n            while(i < n && pairs[i].first >= x) {\n                //for all those pairs which satisfy above condition now we need 2 more things\n                //nums2[i] >= y and maximum sum among all those pairs\n                int sum = pairs[i].first + pairs[i].second;\n                //it can be achieved by monotonic stack\n                //we pass nums2[i] and nums1[i]+nums2[i]\n                update(stack,pairs[i].second,sum);\n                i++;\n            }\n            // for(auto &x : stack) cout << x.first << \' \' << x.second << endl;\n            int ind = lower_bound(stack.begin(),stack.end(),pair<int,int>{y,INT_MIN}) - stack.begin();\n            // cout << stack.size() << endl;\n            if(ind != stack.size()) res[res_ind] = stack[ind].second;\n        }\n        return res;\n    }\n};\n```
['C++']