Longest Subsequence With Limited Sum

Problem

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.

Examples

Example 1:

Input: nums = [4,5,2,1], queries = [3,10,21]
Output: [2,3,4]
Explanation: We answer the queries as follows:
- The subsequence [2,1] has a sum less than or equal to 3. It can be proven that 2 is the maximum size of such a subsequence, so answer[0] = 2.
- The subsequence [4,5,1] has a sum less than or equal to 10. It can be proven that 3 is the maximum size of such a subsequence, so answer[1] = 3.
- The subsequence [4,5,2,1] has a sum less than or equal to 21. It can be proven that 4 is the maximum size of such a subsequence, so answer[2] = 4.

Example 2:

Input: nums = [2,3,4,5], queries = [1]
Output: [0]
Explanation: The empty subsequence is the only subsequence that has a sum less than or equal to 1, so answer[0] = 0.

Solution

Method 1 – Greedy + Prefix Sum + Binary Search

Intuition

To maximize the subsequence size under a sum limit, always pick the smallest numbers first. Sorting nums and using prefix sums allows us to quickly find, for each query, the largest prefix whose sum does not exceed the query value.

Approach

1. Sort the nums array in ascending order.
2. Compute the prefix sum array of nums.
3. For each query:

• Use binary search to find the largest index k such that the prefix sum at k is less than or equal to the query value.
• The answer for that query is k (number of elements).

4. Return the list of answers.

Code

C++

class Solution {
public:
   vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {
      sort(nums.begin(), nums.end());
      int n = nums.size();
      vector<int> pre(n + 1, 0), ans;
      for (int i = 0; i < n; ++i)
        pre[i + 1] = pre[i] + nums[i];
      for (int q : queries) {
        int l = 0, r = n;
        while (l < r) {
           int m = (l + r + 1) / 2;
           if (pre[m] <= q) l = m;
           else r = m - 1;
        }
        ans.push_back(l);
      }
      return ans;
   }
};

Go

type Solution struct{}

func (Solution) AnswerQueries(nums []int, queries []int) []int {
   sort.Ints(nums)
   n := len(nums)
   pre := make([]int, n+1)
   for i := 0; i < n; i++ {
      pre[i+1] = pre[i] + nums[i]
   }
   ans := make([]int, len(queries))
   for i, q := range queries {
      l, r := 0, n
      for l < r {
        m := (l + r + 1) / 2
        if pre[m] <= q {
           l = m
        } else {
           r = m - 1
        }
      }
      ans[i] = l
   }
   return ans
}

Java

class Solution {
   public int[] answerQueries(int[] nums, int[] queries) {
      Arrays.sort(nums);
      int n = nums.length;
      int[] pre = new int[n + 1];
      for (int i = 0; i < n; ++i)
        pre[i + 1] = pre[i] + nums[i];
      int[] ans = new int[queries.length];
      for (int i = 0; i < queries.length; ++i) {
        int l = 0, r = n;
        while (l < r) {
           int m = (l + r + 1) / 2;
           if (pre[m] <= queries[i]) l = m;
           else r = m - 1;
        }
        ans[i] = l;
      }
      return ans;
   }
}

Kotlin

class Solution {
   fun answerQueries(nums: IntArray, queries: IntArray): IntArray {
      nums.sort()
      val pre = IntArray(nums.size + 1)
      for (i in nums.indices) {
        pre[i + 1] = pre[i] + nums[i]
      }
      return queries.map { q ->
        var l = 0
        var r = nums.size
        while (l < r) {
           val m = (l + r + 1) / 2
           if (pre[m] <= q) l = m else r = m - 1
        }
        l
      }.toIntArray()
   }
}

Python

class Solution:
   def answerQueries(self, nums: list[int], queries: list[int]) -> list[int]:
      nums.sort()
      pre = [0]
      for x in nums:
        pre.append(pre[-1] + x)
      ans: list[int] = []
      n = len(nums)
      for q in queries:
        l, r = 0, n
        while l < r:
           m = (l + r + 1) // 2
           if pre[m] <= q:
              l = m
           else:
              r = m - 1
        ans.append(l)
      return ans

Rust

impl Solution {
   pub fn answer_queries(nums: Vec<i32>, queries: Vec<i32>) -> Vec<i32> {
      let mut nums = nums;
      nums.sort();
      let n = nums.len();
      let mut pre = vec![0; n + 1];
      for i in 0..n {
        pre[i + 1] = pre[i] + nums[i];
      }
      queries.iter().map(|&q| {
        let (mut l, mut r) = (0, n);
        while l < r {
           let m = (l + r + 1) / 2;
           if pre[m] <= q {
              l = m;
           } else {
              r = m - 1;
           }
        }
        l as i32
      }).collect()
   }
}

Complexity

• Time: O(n log n + m log n) where n is the length of nums and m is the number of queries.
• Space: O(n) for the prefix sum array.