hi, let Avik connect you.
** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.
** You can check all the posts on the Posts page.
** More about me in the About Me section.
Longest Subsequence With Limited Sum
Problem: 2389. Longest Subsequence With Limited Sum
Problem Link: leetcode.com/problems/longest-subsequence-with-limited-sum/
Approach:
Solved this problem using in O(QxN) and O(Qlog₂N) approach.
Sorted the numbers in the `nums` array.
In O(N²) approach, For each query, kept moving by summing up each element in `nums` until the sum reached `query[i]`.
Count how many numbers are required to reach `query[i]`.
In the O(Nlog₂N) approach, calculated cumulative sum of the `nums` array.
Now, for each query, run a `upper_bound` to check the index where we can find the cumulative sum nearest to `query[i]`.
Insert this count for each `query[i]` in the resultant array.
Return the resultant array.
Time and Space Complexity:
Time Complexity: O(Qlog₂N)
Space Complexity: O(1)
Code [C++] O(QxN)
class Solution {
public:
vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {
sort(nums.begin(), nums.end());
int m = queries.size(), n = nums.size();
for(int i=0; i<m; i++){
int max_sum = queries[i], counter = 0;
for(int j=0; j<n; j++){
if(nums[j] > max_sum) break;
max_sum -= nums[j]; counter++;
}
queries[i] = counter;
}
return queries;
}
};
Code [C++] O(Qlog₂N)
class Solution {
public:
vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {
sort(nums.begin(), nums.end());
int m = queries.size(), n = nums.size();
for(int i=1; i<n; i++){
nums[i] += nums[i-1];
}
for(int i=0; i<m; i++){
int max_sum = queries[i], counter = 0;
int ubound = upper_bound(nums.begin(), nums.end(), max_sum) - nums.begin();
queries[i] = ubound;
}
return queries;
}
};