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 <stdio.h>
2#include <stdlib.h>
3
4int compare(const void *a, const void *b) {
5 return (*(int*)a - *(int*)b);
6}
7
8int* answerQueries(int* nums, int numsSize, int* queries, int queriesSize, int* returnSize) {
9 qsort(nums, numsSize, sizeof(int), compare);
10
11 int* prefixSum = (int*)malloc(numsSize * sizeof(int));
12 prefixSum[0] = nums[0];
13 for (int i = 1; i < numsSize; i++) {
14 prefixSum[i] = prefixSum[i - 1] + nums[i];
15 }
16
17 int* answer = (int*)malloc(queriesSize * sizeof(int));
18 for (int i = 0; i < queriesSize; i++) {
19 int q = queries[i];
20 int count = 0;
21 for (int j = 0; j < numsSize; j++) {
22 if (prefixSum[j] <= q) {
23 count = j + 1;
24 } else {
25 break;
26 }
27 }
28 answer[i] = count;
29 }
30
31 *returnSize = queriesSize;
32 free(prefixSum);
33 return answer;
34}This C solution first sorts the nums array. Then, it computes the prefix sums, allowing us to easily check how many elements from the start can be summed without exceeding the query value. The output is prepared as an array of maximum sizes of these subsequences.
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
The Java implementation uses a manual binary search to find the correct position in the prefix sum array for each query, effectively determining the maximum subsequence size that fits.