Longest Subsequence With Limited Sum

Medium
1080.

Longest Subsequence With Limited Sum

Longest Subsequence With Limited Sum is a medium coding problem on arrays, sorting and greedy, asked in Amazon, Google and Adobe interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number[]} queries
 * @return {number[]}
 */
var answerQueries = function(nums, queries) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Longest Subsequence With Limited Sum — Problem & Solution

Longest Subsequence With Limited Sum solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Longest Subsequence With Limited Sum is a medium coding problem on arrays, sorting and greedy, asked in Amazon, Google and Adobe interviews.

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

Hints for Longest Subsequence With Limited Sum

  1. Hint 1

    Order does not matter for a subsequence's sum, so to fit the most elements, take the smallest ones.

  2. Hint 2

    Sort nums and build prefix sums; the answer for a query is how far into the prefix you can go.

  3. Hint 3

    That last step is a binary search on the prefix sums, which are increasing.

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

  1. Sort nums ascending and compute pre[i] = sum of the first i elements.
  2. For each query, binary-search the largest i with pre[i] <= query.
  3. 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]

Java

public static int[] answerQueries(int[] nums, int[] queries) {
    int[] sorted = nums.clone();
    Arrays.sort(sorted);
    int n = sorted.length;
    int[] pre = new int[n + 1];
    for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + sorted[i];
    int[] out = new int[queries.length];
    for (int q = 0; q < queries.length; q++) {
        int lo = 0, hi = n;
        while (lo < hi) {
            int mid = (lo + hi + 1) >>> 1;
            if (pre[mid] <= queries[q]) lo = mid;
            else hi = mid - 1;
        }
        out[q] = lo;
    }
    return out;
}

C++

vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {
    vector<int> sorted = nums;
    sort(sorted.begin(), sorted.end());
    int n = (int) sorted.size();
    vector<int> pre(n + 1, 0);
    for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + sorted[i];
    vector<int> out;
    for (int q : queries) {
        int lo = 0, hi = n;
        while (lo < hi) {
            int mid = (lo + hi + 1) / 2;
            if (pre[mid] <= q) lo = mid;
            else hi = mid - 1;
        }
        out.push_back(lo);
    }
    return out;
}

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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms