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.
1import java.util.Arrays;
2
3public class Solution {
4 public int[] answerQueries(int[] nums, int[] queries) {
5 Arrays.sort(nums);
6 int[] prefixSum = new int[nums.length];
7 prefixSum[0] = nums[0];
8 for (int i = 1; i < nums.length; i++) {
9 prefixSum[i] = prefixSum[i - 1] + nums[i];
10 }
11
12 int[] answer = new int[queries.length];
13 for (int i = 0; i < queries.length; i++) {
14 int count = 0;
15 for (int j = 0; j < nums.length; j++) {
16 if (prefixSum[j] <= queries[i]) {
17 count = j + 1;
18 } else {
19 break;
20 }
21 }
22 answer[i] = count;
23 }
24 return answer;
25 }
26}This Java solution follows the same logic as in other languages; it sorts the nums list and constructs prefix sums. It iteratively checks each query against the prefix sums to determine the maximum 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.
1
public class Solution {
public int[] AnswerQueries(int[] nums, int[] queries) {
Array.Sort(nums);
int n = nums.Length;
for (int i = 1; i < n; i++) {
nums[i] += nums[i-1];
}
int[] answer = new int[queries.Length];
for (int i = 0; i < queries.Length; i++) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] <= queries[i]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
answer[i] = left;
}
return answer;
}
}This C# solution mirrors a binary search approach to determine the correct length of the subsequence allowed for each query based on previously computed prefix sums. The prefix sums are stored in the same array to save space.