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.
1from bisect import bisect_right
2
3class Solution:
4 def answerQueries(self, nums, queries):
5 nums.sort()
6 prefix_sum = [0] * len(nums)
7 prefix_sum[0] = nums[0]
8 for i in range(1, len(nums)):
9 prefix_sum[i] = prefix_sum[i - 1] + nums[i]
10
11 answer = []
12 for q in queries:
13 count = bisect_right(prefix_sum, q)
14 answer.append(count)
15 return answerThe Python solution makes use of bisect_right to find the breakpoint in the prefix sums for each query, providing the maximum size of a subsequence that fits.
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 JavaScript solution uses an in-place binary search on the prefix sums to find the largest number of elements that can fit for each query value, optimizing the search process significantly compared to linear iteration.