Longest Subsequence With Limited Sum
EasyPrompt
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.
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.
Constraints:
n == nums.lengthm == queries.length1 <= n, m <= 10001 <= nums[i], queries[i] <= 106
Approaches
3 approaches with complexity analysis and trade-offs.
This approach iterates through each query and, for each one, sorts the nums array to greedily pick the smallest elements. This is highly inefficient because the sorting operation is repeated for every single query.
Algorithm
- Initialize an answer array
ansof sizem. - For each query
queries[i]fromi = 0tom-1:- Create a copy of
numsand sort it. - Initialize
count = 0andcurrentSum = 0. - Iterate through the sorted
numsarray. - For each
numin the sorted array:- If
currentSum + num <= queries[i], addnumtocurrentSumand incrementcount. - Otherwise, break the loop.
- If
- Set
ans[i] = count.
- Create a copy of
- Return
ans.
Walkthrough
The core idea to maximize the subsequence size for a given sum is to always pick the smallest available numbers. This approach applies this greedy strategy directly for each query.
For every query q in queries:
- A copy of the
numsarray is sorted in non-decreasing order. - We iterate through the sorted numbers, accumulating their sum and counting how many elements we've taken.
- We stop when adding the next number would exceed the query limit
q. - The final count for that query is stored.
This process is repeated for all queries, leading to a high time complexity due to the repeated sorting.
import java.util.Arrays; class Solution { public int[] answerQueries(int[] nums, int[] queries) { int m = queries.length; int[] answer = new int[m]; for (int i = 0; i < m; i++) { int query = queries[i]; int[] sortedNums = Arrays.copyOf(nums, nums.length); Arrays.sort(sortedNums); int count = 0; int currentSum = 0; for (int num : sortedNums) { if (currentSum + num <= query) { currentSum += num; count++; } else { break; } } answer[i] = count; } return answer; }}Complexity
Time
O(m * n log n), where `n` is the number of elements in `nums` and `m` is the number of queries. For each of the `m` queries, we sort `nums` in O(n log n) time.
Space
O(n) to store a copy of the `nums` array for sorting. The space for the answer array is O(m).
Trade-offs
Pros
Simple to understand and implement.
Cons
Very inefficient due to repeated sorting, especially for a large number of queries.
Performs a lot of redundant work.
This approach improves upon the brute-force method by recognizing that the nums array only needs to be sorted once. After an initial sort, we can iterate through the sorted array for each query to find the answer.
Algorithm
- Sort the
numsarray in non-decreasing order. - Initialize an answer array
ansof sizem. - For each query
queries[i]fromi = 0tom-1:- Initialize
count = 0andcurrentSum = 0. - Iterate through the now-sorted
numsarray. - For each
numinnums:- If
currentSum + num <= queries[i], addnumtocurrentSumand incrementcount. - Otherwise, break the loop.
- If
- Set
ans[i] = count.
- Initialize
- Return
ans.
Walkthrough
The key observation is that to maximize the subsequence length, we should always pick the smallest elements. The optimal order of elements to pick is always the same, regardless of the query sum limit.
Therefore, we can sort the nums array just one time at the beginning. After sorting, for each query q, we perform a linear scan through the sorted nums array. We add elements to our subsequence and keep a running sum. We stop when the sum exceeds q. The number of elements added is the answer for that query. This avoids the expensive O(n log n) sorting operation inside the query loop.
import java.util.Arrays; class Solution { public int[] answerQueries(int[] nums, int[] queries) { Arrays.sort(nums); int n = nums.length; int m = queries.length; int[] answer = new int[m]; for (int i = 0; i < m; i++) { int query = queries[i]; int count = 0; int currentSum = 0; for (int j = 0; j < n; j++) { if (currentSum + nums[j] <= query) { currentSum += nums[j]; count++; } else { break; } } answer[i] = count; } return answer; }}Complexity
Time
O(n log n + m * n). Sorting takes O(n log n). Then, for each of the `m` queries, we iterate up to `n` times.
Space
O(log n) or O(n) for sorting, plus O(m) for the answer array. Typically stated as O(n) to include the answer array and potential sorting space.
Trade-offs
Pros
Much more efficient than the first approach.
The logic remains straightforward.
Cons
Can still be slow if both
nandmare large, as the complexity is dominated by them * nterm.
This is the most efficient approach. It involves pre-calculating the prefix sums of the sorted nums array. For each query, we can then use binary search on the prefix sum array to find the answer in logarithmic time.
Algorithm
- Sort the
numsarray. - Create a prefix sum array from the sorted
nums. This can be done in-place. - Initialize an answer array
ansof sizem. - For each query
queries[i]:- Perform a binary search on the prefix sum array to find the count of elements whose sum is less than or equal to
queries[i]. - This is equivalent to finding the rightmost index
jsuch thatprefix[j] <= queries[i]. The answer isj + 1. - Store this count in
ans[i].
- Perform a binary search on the prefix sum array to find the count of elements whose sum is less than or equal to
- Return
ans.
Walkthrough
This method builds on the insight that we should always pick the smallest elements.
- First, sort the
numsarray. - Next, compute the prefix sums of the sorted array. The
i-th element of the prefix sum array will store the sum of the firsti+1smallest numbers fromnums. We can do this in-place to save space. Letnums[i]becomenums[0] + ... + nums[i]. - Now, for each query
q, the problem is transformed into finding the maximum lengthksuch that the sum of theksmallest elements is less than or equal toq. This is equivalent to finding the largest indexjin the prefix sum array such thatprefix[j] <= q. The answer for the query will then bej + 1. - Since the prefix sum array is monotonically increasing, we can efficiently find this for each query using binary search.
import java.util.Arrays; class Solution { public int[] answerQueries(int[] nums, int[] queries) { // 1. Sort nums Arrays.sort(nums); int n = nums.length; int m = queries.length; // 2. Create prefix sums in-place for (int i = 1; i < n; i++) { nums[i] += nums[i - 1]; } int[] answer = new int[m]; // 3. For each query, binary search for the answer for (int i = 0; i < m; i++) { int query = queries[i]; int count = binarySearch(nums, query); answer[i] = count; } return answer; } // This binary search finds the number of prefix sums less than or equal to target. private int binarySearch(int[] arr, int target) { int left = 0, right = arr.length - 1; int ans = 0; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] <= target) { // This length (mid + 1) is a possible answer. // Try for a longer subsequence. ans = mid + 1; left = mid + 1; } else { // The sum is too large, try a shorter subsequence. right = mid - 1; } } return ans; }}Complexity
Time
O(n log n + m log n). O(n log n) for sorting, O(n) for prefix sums, and O(m * log n) for `m` binary searches.
Space
O(log n) or O(n) for sorting. If modifying `nums` in-place, no extra space is needed for prefix sums. The answer array takes O(m). Overall, O(n) is a safe upper bound.
Trade-offs
Pros
Highly efficient and optimal for the given constraints.
Scales well with a large number of queries.
Cons
Slightly more complex to implement due to the prefix sum calculation and binary search logic.
Solutions
Solution
class Solution: def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]: nums . sort() s = list(accumulate(nums)) return [bisect_right(s, q) for q in queries]public class Solution { public int[] AnswerQueries(int[] nums, int[] queries) { int[] result = new int[queries.Length]; Array.Sort(nums); for (int i = 0; i < queries.Length; i++) { result[i] = getSubsequent(nums, queries[i]); } return result; } public int getSubsequent(int[] nums, int query) { int sum = 0; for (int i = 0; i < nums.Length; i++) { sum += nums[i]; if (sum > query) { return i; } } return nums.Length; }}class Solution {public int[] answerQueries(int[] nums, int[] queries) { Arrays.sort(nums); for (int i = 1; i < nums.length; ++i) { nums[i] += nums[i - 1]; } int m = queries.length; int[] ans = new int[m]; for (int i = 0; i < m; ++i) { ans[i] = search(nums, queries[i]); } return ans; }private int search(int[] nums, int x) { int l = 0, r = nums.length; while (l < r) { int mid = (l + r) >> 1; if (nums[mid] > x) { r = mid; } else { l = mid + 1; } } return l; }}/** * @param {number[]} nums * @param {number[]} queries * @return {number[]} */ var answerQueries = function (nums, queries) { nums.sort((a, b) => a - b); for (let i = 1; i < nums.length; i++) { nums[i] += nums[i - 1]; } return queries.map((q) => _.sortedIndex(nums, q + 1)); };class Solution {public: vector<int> answerQueries(vector<int> &nums, vector<int> &queries) { sort(nums.begin(), nums.end()); for (int i = 1; i < nums.size(); i++) { nums[i] += nums[i - 1]; } vector<int> ans; for (auto &q : queries) { ans.push_back(upper_bound(nums.begin(), nums.end(), q) - nums.begin()); } return ans; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.