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] <= 106Problem Overview: You get an integer array nums and multiple query values. For each query, return the maximum length of a subsequence whose total sum is less than or equal to that query. The subsequence can contain any elements from the array but must respect the sum constraint.
Approach 1: Greedy with Sorting and Prefix Sum (Time: O(n log n + n·q), Space: O(n))
The key observation: to maximize subsequence length under a sum limit, you should always pick the smallest numbers first. Sort the array using sorting. After sorting, compute a prefix sum array where prefix[i] represents the sum of the smallest i+1 numbers. For each query, iterate through the prefix array and find the largest index where the prefix sum is ≤ the query value. That index + 1 is the maximum subsequence length you can build.
This works because any larger number would increase the sum faster and reduce how many elements you can include. The greedy choice of always taking the smallest available numbers guarantees the longest valid subsequence. This approach is easy to implement but scanning the prefix array for every query leads to O(n) work per query.
Approach 2: Binary Search on Prefix Sums (Time: O(n log n + q log n), Space: O(n))
After sorting the array and building the prefix sums, the prefix array becomes monotonically increasing. That property allows you to apply binary search. For each query, perform a binary search on the prefix array to find the rightmost index where prefix[i] ≤ query. The position of that index determines the maximum number of elements you can include.
Binary search reduces each query from O(n) to O(log n). The preprocessing step (sorting and building prefix sums) still takes O(n log n), but query handling becomes much faster for large input sizes. This pattern—sort → prefix sum → binary search—is common in problems where you repeatedly check cumulative limits.
Recommended for interviews: Start by explaining the greedy idea: choosing the smallest numbers maximizes how many elements fit under the sum constraint. Build prefix sums to track cumulative totals. The optimal implementation uses binary search on the prefix array, achieving O(n log n + q log n). Mentioning the linear scan version first shows you understand the structure of the problem, while the binary search optimization demonstrates strong knowledge of array processing and query optimization.
By sorting the nums array, the subsequences with the smallest sums can be easily constructed. Calculating a prefix sum for the sorted array helps in determining how many elements can be included before the sum exceeds the query limit.
This C solution first sorts the nums array. Then, it computes the prefix sums, allowing us to easily check how many elements from the start can be summed without exceeding the query value. The output is prepared as an array of maximum sizes of these subsequences.
Time Complexity: O(n log n + m * n), where n is the length of nums and m is the length of queries.
Space Complexity: O(n) for the prefix sum array.
This approach extends the prefix sum method by using binary search to efficiently find where the query fits within the prefix sum array. This reduces the time complexity significantly, especially for large inputs.
This C code implements binary search on the prefix sum array to quickly determine how many elements from the sorted array have a sum that fits within the query limit. This is more efficient than iterating linearly.
Time Complexity: O(n log n + m log n), where n is the length of nums and m is the length of queries.
Space Complexity: O(n) for the prefix sum array.
According to the problem description, for each queries[i], we need to find a subsequence such that the sum of its elements does not exceed queries[i] and the length of the subsequence is maximized. Obviously, we should choose the smallest possible elements to maximize the length of the subsequence.
Therefore, we can first sort the array nums in ascending order, and then for each queries[i], we can use binary search to find the smallest index j such that nums[0] + nums[1] + cdots + nums[j] > queries[i]. At this point, nums[0] + nums[1] + cdots + nums[j - 1] is the sum of the elements of the subsequence that meets the condition, and the length of this subsequence is j. Therefore, we can add j to the answer array.
The time complexity is O((n + m) times log n), and the space complexity is O(n) or O(log n). Here, n and m are the lengths of the arrays nums and queries, respectively.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
Similar to Solution 1, we can first sort the array nums in ascending order.
Next, we define an index array idx of the same length as queries, where idx[i] = i. Then, we sort the array idx in ascending order based on the values in queries. This way, we can process the elements in queries in ascending order.
We use a variable s to record the sum of the currently selected elements and a variable j to record the number of currently selected elements. Initially, s = j = 0.
We traverse the index array idx, and for each index i in it, we iteratively add elements from the array nums to the current subsequence until s + nums[j] \gt queries[i]. At this point, j is the length of the subsequence that meets the condition. We set the value of ans[i] to j and then continue to process the next index.
After traversing the index array idx, we obtain the answer array ans, where ans[i] is the length of the subsequence that satisfies queries[i].
The time complexity is O(n times log n + m), and the space complexity is O(m). Here, n and m are the lengths of the arrays nums and queries, respectively.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Greedy Approach with Sorting and Prefix Sum | Time Complexity: O(n log n + m * n), where n is the length of |
| Binary Search Optimization | Time Complexity: O(n log n + m log n), where n is the length of |
| Sorting + Prefix Sum + Binary Search | — |
| Sorting + Offline Query + Two Pointers | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Sorting + Prefix Sum (Linear Scan) | O(n log n + n·q) | O(n) | Simple implementation when the number of queries is small |
| Prefix Sum + Binary Search | O(n log n + q log n) | O(n) | Best for large query counts; efficient lookups using sorted prefix sums |
Longest Subsequence With Limited Sum : Explanation ➕ Live Coding👩🏻💻🧑🏻💻🤯😱 • codestorywithMIK • 6,394 views views
Watch 9 more video solutions →Practice Longest Subsequence With Limited Sum with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor