2389. Longest Subsequence With Limited Sum
Description
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
Solutions
Solution 1: Sorting + Prefix Sum + Binary Search
According to the problem description, for each $\textit{queries[i]}$, we need to find a subsequence such that the sum of its elements does not exceed $\textit{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 $\textit{nums}$ in ascending order, and then for each $\textit{queries[i]}$, we can use binary search to find the smallest index $j$ such that $\textit{nums}[0] + \textit{nums}[1] + \cdots + \textit{nums}[j] > \textit{queries[i]}$. At this point, $\textit{nums}[0] + \textit{nums}[1] + \cdots + \textit{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 $\textit{nums}$ and $\textit{queries}$, respectively.
Python3
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]
Java
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) {
int j = Arrays.binarySearch(nums, queries[i] + 1);
ans[i] = j < 0 ? -j - 1 : j;
}
return ans;
}
}
C++
class Solution {
public:
vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {
ranges::sort(nums);
for (int i = 1; i < nums.size(); i++) {
nums[i] += nums[i - 1];
}
vector<int> ans;
for (const auto& q : queries) {
ans.emplace_back(upper_bound(nums.begin(), nums.end(), q) - nums.begin());
}
return ans;
}
};
Go
func answerQueries(nums []int, queries []int) (ans []int) {
sort.Ints(nums)
for i := 1; i < len(nums); i++ {
nums[i] += nums[i-1]
}
for _, q := range queries {
ans = append(ans, sort.SearchInts(nums, q+1))
}
return
}
TypeScript
function answerQueries(nums: number[], queries: number[]): number[] {
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));
}
Rust
impl Solution {
pub fn answer_queries(mut nums: Vec<i32>, queries: Vec<i32>) -> Vec<i32> {
nums.sort();
for i in 1..nums.len() {
nums[i] += nums[i - 1];
}
queries.iter().map(|&q| {
match nums.binary_search(&q) {
Ok(idx) => idx as i32 + 1,
Err(idx) => idx as i32,
}
}).collect()
}
}
JavaScript
/**
* @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));
};
C#
public class Solution {
public int[] AnswerQueries(int[] nums, int[] queries) {
Array.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) {
int j = Array.BinarySearch(nums, queries[i] + 1);
ans[i] = j < 0 ? -j - 1 : j;
}
return ans;
}
}
Solution 2: Sorting + Offline Query + Two Pointers
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.
Python3
class Solution:
def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
nums.sort()
m = len(queries)
ans = [0] * m
idx = sorted(range(m), key=lambda i: queries[i])
s = j = 0
for i in idx:
while j < len(nums) and s + nums[j] <= queries[i]:
s += nums[j]
j += 1
ans[i] = j
return ans
Java
class Solution {
public int[] answerQueries(int[] nums, int[] queries) {
Arrays.sort(nums);
int m = queries.length;
Integer[] idx = new Integer[m];
for (int i = 0; i < m; ++i) {
idx[i] = i;
}
Arrays.sort(idx, (i, j) -> queries[i] - queries[j]);
int[] ans = new int[m];
int s = 0, j = 0;
for (int i : idx) {
while (j < nums.length && s + nums[j] <= queries[i]) {
s += nums[j++];
}
ans[i] = j;
}
return ans;
}
}
C++
class Solution {
public:
vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {
sort(nums.begin(), nums.end());
int m = queries.size();
vector<int> idx(m);
iota(idx.begin(), idx.end(), 0);
sort(idx.begin(), idx.end(), [&](int i, int j) {
return queries[i] < queries[j];
});
vector<int> ans(m);
int s = 0, j = 0;
for (int i : idx) {
while (j < nums.size() && s + nums[j] <= queries[i]) {
s += nums[j++];
}
ans[i] = j;
}
return ans;
}
};
Go
func answerQueries(nums []int, queries []int) (ans []int) {
sort.Ints(nums)
m := len(queries)
idx := make([]int, m)
for i := range idx {
idx[i] = i
}
sort.Slice(idx, func(i, j int) bool { return queries[idx[i]] < queries[idx[j]] })
ans = make([]int, m)
s, j := 0, 0
for _, i := range idx {
for j < len(nums) && s+nums[j] <= queries[i] {
s += nums[j]
j++
}
ans[i] = j
}
return
}
TypeScript
function answerQueries(nums: number[], queries: number[]): number[] {
nums.sort((a, b) => a - b);
const m = queries.length;
const idx: number[] = new Array(m);
for (let i = 0; i < m; i++) {
idx[i] = i;
}
idx.sort((i, j) => queries[i] - queries[j]);
const ans: number[] = new Array(m);
let s = 0;
let j = 0;
for (const i of idx) {
while (j < nums.length && s + nums[j] <= queries[i]) {
s += nums[j++];
}
ans[i] = j;
}
return ans;
}