< Back





2389. Longest Subsequence With Limited Sum

Given an array of integers and an array of queries, we're asked to find the maximum size of the
subsequence of numbers we can select from nums that will sum to at most the value at queries[j]. The
input is nums is not sorted.

To solve this quickly, we sort the input, nums, in O(nlog(n)) time and acquire its prefix sum. Now,
each num in nums is sorted in ascending order, and each num is the sum of all prefixes before it.
From here, we can binary search for the largest prefix sum that is less than or equal to queries[j].

The solution is as follows:


  class Solution:
      def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
          nums.sort()

          for i in range(1, len(nums)):
              nums[i] += nums[i - 1]

          ans, n = [], len(nums)

          for j in range(len(queries)):
              l, r = 0, n - 1

              while l <= r:
                  m = (r + l) // 2

                  if nums[m] <= queries[j]:
                      l = m + 1
                  else:
                      r = m - 1

              ans.append(l)

          return ans


_ Time Complexity:

  O((m + n)log(n)) - We have to sort the input and acquire the prefix sum in O(nlog(n)) time. Then,
  for m iterations, we conduct binary search in log(n) time.

_ Space Complexity:

  O(n) - Python sorting requires O(n) space.