Problem URL: Longest subsequence with limited sum

We will sort the numbers and then create a prefix sum array. Then we will iterate over the numbers and find the index of the largest number that is less than or equal to limit - nums[i]. We will update the result.

class Solution:
    def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
        nums.sort()
        prefix = [0]
        for num in nums:
            prefix.append(prefix[-1]+num)

        res = []
        for query in queries:
            idx = bisect.bisect_right(nums, query)
            res.append(idx-1)

        return res

Time complexity: O(nlog(n))
Space complexity: O(n)

We can do the same thing using python's built in methods.

class Solution:
    def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
        nums = list(accumulate(sorted(nums)))
        return [bisect_right(nums, q) for q in queries]