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] <= 106By 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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.
| 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 |
Longest Subsequence With Limited Sum : Explanation ➕ Live Coding👩🏻💻🧑🏻💻🤯😱 • codestorywithMIK • 3,800 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