Longest Subsequence With Limited Sum

easy binary search prefix sum sorting

Problem

Given an array nums and an array of queries, answer each query independently: return the maximum number of elements you can pick from nums (in any order, a subsequence) so that their sum does not exceed the query value. To fit the most elements under a budget you should greedily take the smallest values, so sort nums, build prefix sums, and for each query binary search the longest prefix whose sum stays within the limit.

Inputnums = [4, 5, 2, 1], queries = [3, 10, 21]

Output[2, 3, 4]

Sorted nums = [1, 2, 4, 5], prefix = [1, 3, 7, 12]. For 3 the longest prefix ≤ 3 is [1, 2] (length 2); for 10 it is [1, 2, 4] = 7 (length 3); for 21 all four fit (length 4).

nums (comma-separated)

queries

from bisect import bisect_right
def answer_queries(nums, queries):
    nums.sort()
    prefix = []
    total = 0
    for x in nums:
        total += x
        prefix.append(total)
    out = []
    for q in queries:
        out.append(bisect_right(prefix, q))
    return out

function answerQueries(nums, queries) {
  nums.sort((a, b) => a - b);
  const prefix = [];
  let total = 0;
  for (const x of nums) { total += x; prefix.push(total); }
  return queries.map(q => {
    let l = 0, r = prefix.length;
    while (l < r) { const m = (l + r) >> 1; if (prefix[m] <= q) l = m + 1; else r = m; }
    return l;
  });
}

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

vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {
    sort(nums.begin(), nums.end());
    vector<int> prefix(nums.size());
    int total = 0;
    for (int i = 0; i < (int)nums.size(); i++) { total += nums[i]; prefix[i] = total; }
    vector<int> ans(queries.size());
    for (int i = 0; i < (int)queries.size(); i++) {
        int l = 0, r = (int)prefix.size();
        while (l < r) { int m = (l + r) / 2; if (prefix[m] <= queries[i]) l = m + 1; else r = m; }
        ans[i] = l;
    }
    return ans;
}

Explanation

A subsequence can pick any elements in any order, and we only care about the count we fit under a sum limit — the positions do not matter. To squeeze in as many numbers as possible for a given budget, always grab the smallest ones first. So the first move is to sort nums ascending.

Once sorted, the best subsequence of size k is simply the first k values, and its sum is the prefix sum at position k. We precompute those running totals once: prefix[i] is the sum of the first i + 1 sorted numbers.

Prefix sums of non-negative numbers are non-decreasing, so they are sorted too. For a query q we want the largest length whose prefix sum is <= q. Because the prefix array is sorted, binary search finds that boundary instantly — it is the count of prefix entries that are <= q (an upper-bound / bisect_right).

Example: nums = [4, 5, 2, 1] sorts to [1, 2, 4, 5] with prefix [1, 3, 7, 12]. Query 3: entries <= 3 are [1, 3] → answer 2. Query 10: [1, 3, 7] → answer 3. Query 21: all four → answer 4. Result [2, 3, 4].

We sort and build the prefix once, then every query is a fast logarithmic lookup, which is far quicker than re-summing the array for each query.

Time: O(n log n + q log n) Space: O(n)