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.
- Difficulty: Medium
- Topics: Arrays, Sorting, Greedy, 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.lengthm == queries.length1 <= n, m <= 10001 <= nums[i], queries[i] <= 10^6
Hints for Longest Subsequence With Limited Sum
Hint 1
Order does not matter for a subsequence's sum, so to fit the most elements, take the smallest ones.
Hint 2
Sort
numsand build prefix sums; the answer for a query is how far into the prefix you can go.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
- Sort
numsascending and computepre[i]= sum of the firstielements. - For each query, binary-search the largest
iwithpre[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]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