Longest Subsequence With Limited Sum — Medium Problem & Solution

For each value in queries, find the maximum length of a subsequence of nums whose sum is at most that value. Return those lengths in order.

Difficulty: Medium
Topics: Arrays, Greedy, Sorting, Binary Search, Prefix Sum
Asked at: Amazon, Google, Adobe
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

For each value in queries, find the maximum length of a subsequence of nums whose sum is at most that value.

Return those lengths in order.

Example 1

Input: nums = [4,5,2,1], queries = [3,10,21]
Output: [2,3,4]
Explanation: `[2,1]`, `[4,2,1]` and the whole array.

Example 2

Input: nums = [2,3,4,5], queries = [1]
Output: [0]
Explanation: Even the smallest element exceeds 1.

Example 3

Input: nums = [1,1,1], queries = [2,5]
Output: [2,3]

Constraints

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

How to solve Longest Subsequence With Limited Sum

Since a subsequence's sum ignores order, the longest one under a budget is always a prefix of the sorted array. Sort, build prefix sums, and binary-search each query for the largest prefix whose sum fits.

Approach

Sort nums ascending and compute pre[i] = sum of the first i elements.
For each query, binary-search the largest i with pre[i] <= query.
Collect those indices as the answers.

Why it works

The exchange argument is immediate: if an optimal selection omits a smaller element while including a larger one, swapping them keeps the length and lowers the sum. So taking the smallest elements first is optimal, and the prefix sums are increasing — which is exactly what makes the binary search valid.

Complexity

Time — O(n log n + m log n)
Space — O(n)

Pitfalls

The queries are independent; the array is not consumed between them.
A subsequence need not be contiguous, which is what licenses the sort.
An answer of 0 is valid when even the smallest element does not fit.

Reference solution

Python

from bisect import bisect_right
from typing import List

def answerQueries(nums: List[int], queries: List[int]) -> List[int]:
    s = sorted(nums)
    pre = [0]
    for v in s:
        pre.append(pre[-1] + v)
    return [bisect_right(pre, q) - 1 for q in queries]

JavaScript

var answerQueries = function(nums, queries) {
    var sorted = nums.slice();
    sorted.sort(function(a, b) { return a - b; });
    var pre = [0], i;
    for (i = 0; i < sorted.length; i++) pre.push(pre[i] + sorted[i]);
    var out = [];
    for (i = 0; i < queries.length; i++) {
        var lo = 0, hi = sorted.length;
        while (lo < hi) {
            var mid = (lo + hi + 1) >> 1;
            if (pre[mid] <= queries[i]) lo = mid; else hi = mid - 1;
        }
        out.push(lo);
    }
    return out;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue