Longest Subsequence With Limited Sum

easy LeetCode #2389
array binary-search greedy sorting prefix-sum

Description

You are given an integer array nums of length n, and an integer array queries of length m. Return an array answer of length m where answer[i] is the maximum size of a subsequence that you can take from nums such that the sum of its elements is less than or equal to queries[i].

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

Example 1:
Input: nums = [4, 5, 2, 1], queries = [3, 10, 21]
Output: [2, 3, 4]
Explanation:
- Query 3: We can take subsequence [2, 1] with sum = 3 <= 3. Maximum size is 2.
- Query 10: We can take subsequence [4, 2, 1] with sum = 7 <= 10, or [5, 2, 1] with sum = 8 <= 10. Maximum size is 3.
- Query 21: We can take all elements [4, 5, 2, 1] with sum = 12 <= 21. Maximum size is 4.

Example 2:
Input: nums = [2, 3, 4, 5], queries = [1]
Output: [0]
Explanation: The smallest element is 2, which is greater than 1. No subsequence has sum <= 1, so the answer is 0.

Constraints

  • n == nums.length
  • m == queries.length
  • 1 <= n, m <= 1000
  • 1 <= nums[i], queries[i] <= 10^6

Complexity

Show Complexity
  • Time: O(n log n + m log n)
  • Space: O(n)

Hints

Show Hints
Pattern
Sort + Prefix Sum + Binary Search
Approach
To maximize subsequence length, greedily pick smallest elements. Sort nums, build prefix sums, then for each query binary search for the largest prefix sum <= query.
Complexity
Sort nums, compute prefix sums, binary search for each query

Solutions

Show PY Solution 
def solution(nums: list[int], queries: list[int]) -> list[int]:
    sorted_nums = sorted(nums)
    sums = [sorted_nums[0]]

    for i in range(1, len(sorted_nums)):
        num = sorted_nums[i]
        sums.append(sums[-1] + num)

    result = []

    for i in range(len(queries)):
        q = queries[i]
        left = 0
        right = len(sums) - 1

        while left <= right:
            mid = left + (right - left) // 2
            v = sums[mid]

            if v <= q:
                left = mid + 1
            else:
                right = mid - 1

        result.append(right + 1)

    return result