Sponsored
Sponsored
By sorting the nums array, the subsequences with the smallest sums can be easily constructed. Calculating a prefix sum for the sorted array helps in determining how many elements can be included before the sum exceeds the query limit.
Time Complexity: O(n log n + m * n), where n is the length of nums and m is the length of queries.
Space Complexity: O(n) for the prefix sum array.
1var answerQueries = function(nums, queries) {
2 nums.sort((a, b) => a - b);
3 for(let i = 1; i < nums.length; i++) {
4 nums[i] += nums[i - 1];
5 }
6
7 return queries.map(q => {
8 let count = 0;
9 for(let sum of nums){
10 if(sum <= q){
11 count++;
12 } else {
13 break;
14 }
15 }
16 return count;
17 });
18};JavaScript uses Array.sort to sort the numbers and computes prefix sums in place. For each query, it iterates through the prefix sums to find the largest feasible subsequence size.
This approach extends the prefix sum method by using binary search to efficiently find where the query fits within the prefix sum array. This reduces the time complexity significantly, especially for large inputs.
Time Complexity: O(n log n + m log n), where n is the length of nums and m is the length of queries.
Space Complexity: O(n) for the prefix sum array.
#include <algorithm>
std::vector<int> answerQueries(std::vector<int>& nums, std::vector<int>& queries) {
std::sort(nums.begin(), nums.end());
std::vector<int> prefixSum(nums);
for (size_t i = 1; i < nums.size(); i++) {
prefixSum[i] += prefixSum[i - 1];
}
std::vector<int> answer(queries.size());
for (size_t i = 0; i < queries.size(); i++) {
int count = std::upper_bound(prefixSum.begin(), prefixSum.end(), queries[i]) - prefixSum.begin();
answer[i] = count;
}
return answer;
}Using the std::upper_bound function, this C++ solution implements a binary search over the prefix sum array, offering a more computationally efficient way of solving the problem for each query.