C++ || sort, partial_sum, upper_bound || fast (14ms)
To maximise the length of subsequence we need to take the smallest elements (std::sort). To avoid recomputing the sum, we compute the prefix sum using std::part
To maximise the length of subsequence we need to take the smallest elements (```std::sort```). To avoid recomputing the sum, we compute the prefix sum using ```std::partial_sum```, and then we can just do binary search using ```std::upper_bound``` to answer the queries.\n\n```\n    vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {\n        sort(begin(nums), end(nums));\n        partial_sum(begin(nums), end(nums), begin(nums));\n        \n        vector<int> ans;\n        ans.reserve(size(queries));\n        for (const int query : queries) {\n            const auto it = upper_bound(begin(nums), end(nums), query);\n            ans.push_back(distance(begin(nums), it));\n        }\n        \n        return ans;\n    }\n```\n\nTime: ```O(n log n + m log n)``` for ```n = size(nums)``` and ```m = size(queries)```. Sorting the input is ```O(n log n)```, the prefix sum is ```O(n)``` and then to answer the queries we need to the ```m``` times binary search ```O(log n)```.\nSpace: ```O(1)``` as the input doesn\'t count, but we could even just rewrite the ```queries``` vector and return that, see below.\n\nThe inplace solution could look like this:\n\n```\n    vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {\n        sort(begin(nums), end(nums));\n        partial_sum(begin(nums), end(nums), begin(nums));\n        transform(begin(queries), end(queries), begin(queries), [&](const int query) {\n            const auto it = upper_bound(begin(nums), end(nums), query);\n            return distance(begin(nums), it);            \n        });\n        return queries;\n    }\n```\n\n\n\n
['C', 'Sorting', 'Binary Tree', 'Prefix Sum']