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.
1#include <vector>
2#include <algorithm>
3
4std::vector<int> answerQueries(std::vector<int>& nums, std::vector<int>& queries) {
5 std::sort(nums.begin(), nums.end());
6 std::vector<int> prefixSum = nums;
7 for (size_t i = 1; i < nums.size(); i++) {
8 prefixSum[i] += prefixSum[i - 1];
9 }
10
11 std::vector<int> answer;
12 for (int q : queries) {
13 int count = std::upper_bound(prefixSum.begin(), prefixSum.end(), q) - prefixSum.begin();
14 answer.push_back(count);
15 }
16 return answer;
17}In this C++ solution, the nums array is sorted and a prefix sum array is constructed. std::upper_bound is used to efficiently find the maximum subsequence length whose sum is less than or equal to each query.
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.
1
This C code implements binary search on the prefix sum array to quickly determine how many elements from the sorted array have a sum that fits within the query limit. This is more efficient than iterating linearly.