c++ | upper_bound | sorting | very easy to understand
Intuition\nwe want to find sum and compare it with each query to get the length. For sum we have to create prefix sum array. After sorting the given array. then
# Intuition\nwe want to find sum and compare it with each query to get the length. For sum we have to create prefix sum array. After sorting the given array. then find upper bound for each query and get our output array ready.\n\n# Approach\n**step 1**: Sort the given array in order to find the length of maximum subsequence obtained so far for each query.\n\n**step 2:** Make prefix sum array for sorted array obtained so that we can get length by playing with the index whenever we get a sum less than or equal to each query.\n\n**step 3:** use upper bound to find index of element in prefix array which is just greater than the query and then store that index into the answer array for that particular query.\n\n**Prerequisite:** upper_bound function \nlet try to understand upper bound with help of an example:\nupper_bound function takes starting iterator, ending iterator of our array on which we want to find upper_bound, and a element for which we want to find upper bound.\n\nvector<int> arr = {3, 6, 7, 8, 10, 11, 15, 26, 32};\n\nupper_bound(arr.begin(), arr.end(), 7);\nthis is going to return iterator on upper bound of 7 which is 8.\n\nupper_bound(arr.begin(), arr.end(), 7) - arr.begin();\nthis will return an index of the upper bound of the given element.\n-> upper_bound in this case return index of 8 which is 3.\n\n\nso upper_bound basically return the interator on index of element just greater than it.\n\nelement       upper_bound\n3              6\n4              6\n5              6\n6              7\n7              8\n8              10\n9              10\n10             11\n11             15\n..             ..\n..             ..\n32             return an iterator pointing to end  (arr.end())\nbecause upper of bound of 32 which is element just greater than 32 does not exist in our vector so it will return us a iterator pointing to end of the vector.\n\n# Complexity\n- Time complexity:\n~ o(n)\n\n- Space complexity:\no(m) size of query vector \n\n# Code\n```\nclass Solution {\npublic:\n    vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {\n        int n = nums.size();\n        sort(nums.begin(), nums.end());\n        for(int i = 1; i < n; i++)\n        {\n            nums[i] = nums[i] + nums[i - 1];\n        }\n        int m = queries.size();\n        vector<int> ans(m);\n        for(int i = 0; i < m; i++)\n        {\n            int ind = upper_bound(nums.begin(), nums.end(), queries[i]) - nums.begin();\n            ans[i] = ind;\n        }\n        return ans;\n    }\n};\n\n```
['C++']