Nice Question || Sorting || MAp ||80% || 80% || Do check it
Intuition\n Describe your first thoughts on how to solve this problem. \n- Guys Nice Question : Devoted my 2 days but okay Now learned a lot ;\n##### Lets discu
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- Guys Nice Question : Devoted my 2 days but okay Now learned a lot ;\n##### Lets discuss how we can approach to this problem :\n- Firstly think if yi of queries would not be there .... \n   -Then How we will solve it :(Question only>=xi)\n    - We will sort our array nums 1 in and then we will search  for our xi ( Sorted: Binary_Search can be applied )\n    -  We will also maintain the suffix sum  which will tell till nums1[i] what is the greatest sum (from i to nums.size()-1) \n    - And then according to that we can tell the answer . Easier one \n\nNow Comes the interesting part by making the yi of queries comes in the picture.\n-   Now Even after sorting nums1 and searching for xi(Binary Search) we have to traverse from nums1[i]>=xi value(sorted of nums1) and check for the maximum which can give the TLE \n- So two changing variables currnetly which can change the sum which is nums1 value and nums2 value \n- But what if we make our queriees dependent on one of the values  by satisfying always one condition   \n- Comes - HOW????\n- So if I sort my queries in descending order and start processing its values then x value is not going to disturb our answer so our answer will be totally dependent on y ;\n### How TO deal with the Yi part :\n- In descending order in queries I will start to travel from the higher values of nums(independent of X as discussed above ) and will go until we find the value less than xi  and start to upadte \n- INside upadte we are handling how to process y value\n- For handling y values I am taking the map\n    - Map first element will contain the num2 value(y value) and second value will contain the sum \n    - As a new value comes lets say j (sum =nums1[j]+nums2[j]) :(currsum= map value current pointer)\n        - if nums2[j] >= current val of map && sum >=currentsum) then there is no use of current val of map we will erase it as when the call will be there for thsi value the higher value is present \n        - if(nums2[j] <current val  && currentsum<sum) Then will do nothing \n        - if(nums2[j]=<current val && currntsum>sum) As there is a value present which has y value gretaer and even the sum equal to greater than coming one Then I will not take this value \n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n    O(NLOGN)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n    O(N)\n# Code\n```\nclass Solution {\npublic:\n// Inserting the y values efficiently\n    void Update_function(map<int,int>& help , int first , int second)\n    {\n        //cout<<"val: "<<first<<" : "<<second<<endl;\n        if(help.size()==0)\n        {\n            help[second] = second+first;\n            return ;\n        }\n        int prev =-1; // Removing the elemnts from teh map \n        // check whether to add the curr element \n        bool add= true ;\n        for( auto it :help)\n        {\n            // If the coming value sum is greater and its nums2  value is greater\n            //then remove that value from the map as we have higher value and greater sum \n            if(it.first<=second && first+second>=it.second)\n            {\n                if(prev!=-1)\n                {\n                    help.erase(prev);\n                }\n                prev = it.first ;\n            }\n//  If there exist nums2 in map whose sum is greater and also nums2  value is greater teh no need to store in map \n            if(it.first>=second && first+second<it.second)\n            {\n                //cout<<it.second<<endl;\n                add= false;\n                break ;\n            }\n        }\n        if(prev!=-1)\n        {\n            help.erase(prev);\n        }\n        // If no higher value present in map tehn add the value in the map \n        if(add)\n        {\n            help[second]= first +second;\n        }\n    }\n    int maximum(map<int,int>& help , int y )\n    {\n// Simply traversing and finding teh maximum \n        auto it = help.lower_bound(y);\n        int ans =-1;\n        while(it!=help.end())\n        {\n            //cout<<it->first<<" : "<<it->second<<endl;\n            ans= max(ans , it->second);\n            it++;\n        }\n        return ans;\n    }\n    vector<int> maximumSumQueries(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {\n        //  Ans vector for storing the answer \n        vector<int> ans(queries.size(),-1) ;\n        // Inserting index in queries\n        for(int i=0 ; i<queries.size() ;i++)\n        {\n            queries[i].push_back(i);\n        }\n        // Sorting the queries \n        sort(queries.begin(), queries.end());\n        vector<pair<int,int>> copy ;\n        for(int i =0;i<nums1.size() ;i++)\n        {\n            copy.push_back({nums1[i], i});\n        }\n        // Sorting the nums1  in descending order :\n        sort(copy.rbegin(), copy.rend());\n        // Map for handling y values \n        map<int,int> help ;// first = nums2 values ,second = sum ;\n        int i=0 ;\n        for( int j =queries.size()-1 ;j>=0 ;j--)\n        {\n            int x = queries[j][0];\n            int y = queries[j][1];\n            int ind = queries[j][2];\n            // if nums1 value is less than x then break \n            while(i<copy.size() && copy[i].first>=x)\n            {\n                int first = copy[i].first;\n                int second = nums2[copy[i].second];     \n                // First = nums1  ans second = nums2\n                // Update will insert teh value in the map \n                Update_function(help , first , second );\n                i++;\n            }\n            // Maximum will tell the answer for this \n            ans[ind]= maximum(help , y);\n        }\n        return ans ;\n    }\n};\n```
['Ordered Map', 'Sorting', 'C++']