Longest Subsequence With Limited Sum

Using a combination of sorting, prefix sum calculation, and binary search can make the solution more efficient. Let’s dive into it:

1. Sorting: Sorting nums in ascending order helps us in quickly identifying how many elements we can include in our subsequence for a given query. This is because if a number x can be included in the sum, then all numbers less than x can also be included.

2. Prefix sum: Calculating the prefix sum of nums helps us in quickly figuring out the total sum of elements from the start of the array to a given index. The prefix sum is an array where the value at index i is the sum of all numbers from nums[0] to nums[i].

3. Binary Search: For each query, we can perform a binary search on the prefix sum array to find the largest index i such that prefix_sum[i] is less than or equal to the query. The i+1 would be the maximum size of the subsequence for the query, since array indices start from 0.

Here is the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
        nums.sort()
        prefix_sum = [0] * len(nums)
        prefix_sum[0] = nums[0]
        for i in range(1, len(nums)):
            prefix_sum[i] = prefix_sum[i - 1] + nums[i]

        result = []
        for q in queries:
            left, right = 0, len(nums) - 1
            while left <= right:
                mid = left + (right - left) // 2
                if prefix_sum[mid] <= q:
                    left = mid + 1
                else:
                    right = mid - 1
            result.append(right + 1)
        return result

In this code, the nums array is first sorted in ascending order, and then the prefix sum array is computed. For each query, a binary search is performed on the prefix sum array to find the largest index i such that prefix_sum[i] is less than or equal to the query. The i+1 is then appended to the result list. The result list is returned at the end.