Longest Subsequence with Limited Sum Solution in C++/Java/Python/JS
Problem 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.
Examples:
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.
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.length
- m == queries.length
- 1 <= n, m <= 1000
- 1 <= nums[i], queries[i] <= 106
Longest Subsequence With Limited Sum Problem
The problem requires us to work with a list of numbers (nums) and process multiple queries. For each query, we need to find the longest subsequence whose sum is less than or equal to the query value. Finally, we store the answer for each query in a result array.
Now that we understand the problem let's focus on Longest Subsequence With Limited Sum Solution.
Brute Force Approach
Intuition:
Think of how you would approach this problem?... You see that the first thing is that we need to operate on the nums. Secondly, we need to find the answer for each query and store the answer in some array that we will return at the end. But first, let's understand the meaning of a subsequence of an array.
What do we mean by the subsequence of an array?
A subsequence is a sequence that we get from an array by removing some elements (or none) while keeping the order of the remaining elements the same.
For example, if nums = [4, 2, 7]:
- [4, 7] is a subsequence (we removed 2, and the order remains the same).
- [2] is a subsequence (we removed 4 and 7).
- [7, 4] is not a subsequence (the order is changed).
Now, to find the answer for each query, think of how you would find the longest subsequence (the most elements we can take) where the sum of selected numbers is less than or equal to query[i].
The naive method to determine the longest valid subsequence involves generating all possible valid subsequences of nums and tracking their length. The process continues until all valid subsequences have been explored and the maximum length among them is recorded.
To find the longest valid subsequence where the sum of selected elements is less than or equal to query[i], we use a recursive approach. Each element in nums has two choices. Either to be included in the subsequence or to be excluded. By exploring all possible subsequences, we can determine the one with the maximum length that satisfies the condition.
Let's understand this:
Case 1: Including the Current Element
If the sum of the selected elements so far, along with nums[j], does not exceed query[i], we can include the current element in the subsequence.
This means we increase both the sum and the length of the subsequence before making a recursive call to process the next element. This choice explores all possibilities where nums[j] contributes to the final valid subsequence.
Case 2: Excluding the Current Element
Regardless of whether nums[j] could be included or not, we also need to explore the scenario where it is excluded from the subsequence. This allows us to consider all possible subsets of nums that do not include nums[j]. In this case, we simply move to the next index without modifying the sum or the length of the subsequence.
By following this approach, we explore all possible subsequences that can be formed, ensuring we find the longest valid one. To store the maximum valid length for a given query, we use a variable max_length, which gets updated whenever we encounter a subsequence that satisfies the condition. Since each query is independent, we repeat this recursive process for every query in the queries array.
Longest Subsequence with Limited Sum example
Input: nums = [1, 2, 1, 5], queries = [2, 3, 4]
Output: [2, 2, 3]
Explanation: query[0] will have longest subsequence of length = 2, [1, 1], query[1] will also have longest subsequence of length =2 [1, 1] while query[2] has longest subsequence of length = 3 [1,2,1].
Initialization:
- n = nums.size() = 4
- m = queries.size() = 3
- answer is initialized as vector<int>(m), which is [0, 0, 0]
- For each query in queries, we call maxLengthOfSubsequences(0, n, nums, queries[i], 0, 0)
Dry Run for queries[0] = 2
We initialize max_length = 0 and call: maxLengthOfSubsequences(0, 4, nums, 2, 0, 0)
Recursive Calls:
- At i = 0, sum = 0, len = 0:
- Include nums[0] = 1 → sum = 1, len = 1
- Recur for i = 1
- Exclude nums[0]
- Recur for i = 1
- At i = 1, sum = 1, len = 1:
- Include nums[1] = 2 (sum exceeds 2) → Not possible
- Exclude nums[1]
- Recur for i = 2
- At i = 2, sum = 1, len = 1:
- Include nums[2] = 1 → sum = 2, len = 2
- Recur for i = 3
- Exclude nums[2]
- Recur for i = 3
- At i = 3, sum = 2, len = 2:
- Include nums[3] = 5 (sum exceeds 2) → Not possible
- Exclude nums[3]
- Recur for i = 4 (Base case reached, max_length = 2)
Final max_length = 2 for queries[0] = 2, stored in answer[0].
Dry Run for queries[1] = 3
We initialize max_length = 0 and call: maxLengthOfSubsequences(0, 4, nums, 3, 0, 0)
- Similar to queries[0], but now sum = 3 allows subsequences:
- [1, 2] (Length = 2)
- [1, 1] (Length = 2)
Final max_length = 2 for queries[1] = 3, stored in answer[1].
Dry Run for queries[2] = 4
We initialize max_length = 0 and call: maxLengthOfSubsequences(0, 4, nums, 4, 0, 0)
- Possible subsequences:
- [1, 2] (Sum = 3, Length = 2)
- [1, 1, 2] (Sum = 4, Length = 3) (Maximum length)
Final max_length = 3 for queries[2] = 4, stored in answer[2].
Final Output: answer = [2, 2, 3]
Steps to write code
Step 1: Define a Recursive Function for Finding Maximum Subsequence Length
- Create a function maxLengthOfSubsequences(i, n, nums, q, sum, len).
- This function will explore all possible subsequences recursively.
- Base Case: If i >= n, update the global variable max_length with the maximum value found so far.
- Recursive Case:
- If adding nums[i] to the sum does not exceed q, include it and recurse with i+1, updating sum and len.
- Exclude nums[i] and move to the next index.
Step 2: Handle Multiple Queries
- Initialize a vector answer[] to store results for each query.
- Iterate through each query, setting max_length = 0 before each computation.
- Call the recursive function for nums and store the maximum subsequence length in answer[].
Step 3: Return the Final Answer Array
- Once all queries have been processed, return the answer[] array containing results for each query.
Brute Force in all languages
Longest Subsequence With Limited Sum solution in c++
class Solution {
public:
// Variable to store maximum subsequence length
int max_length;
// Recursive function to find the longest valid subsequence
void maxLengthOfSubsequences(int i, int n, vector<int>& nums, int q, int sum, int len) {
// Base condition: If we reach the end of the array
if(i >= n) {
// Update max_length if the current length is greater
max_length = max(max_length, len);
return;
}
// Choice 1: Include current element if it does not exceed query limit
if(sum + nums[i] <= q) {
maxLengthOfSubsequences(i+1, n, nums, q, sum + nums[i], len+1);
}
// Choice 2: Exclude current element
maxLengthOfSubsequences(i+1, n, nums, q, sum, len);
}
// Function to process queries and find the longest subsequence for each query
vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {
// Store the size of nums array
int n = nums.size();
// Store the size of queries array
int m = queries.size();
// Answer array to store results
vector<int> answer(m);
// Iterate over each query
for(int i = 0; i < m; ++i) {
// Initialize max_length to 0 for the current query
max_length = 0;
// Call recursive function to find max subsequence length
maxLengthOfSubsequences(0, n, nums, queries[i], 0, 0);
// Store the result for current query
answer[i] = max_length;
}
// Return the answer array
return answer;
}
};Longest Subsequence With Limited Sum solution in java
class Solution {
// Variable to store maximum subsequence length
int max_length;
// Recursive function to find the longest valid subsequence
void maxLengthOfSubsequences(int i, int n, int[] nums, int q, int sum, int len) {
// Base condition: If we reach the end of the array
if(i >= n) {
// Update max_length if the current length is greater
max_length = Math.max(max_length, len);
return;
}
// Choice 1: Include current element if it does not exceed query limit
if(sum + nums[i] <= q) {
maxLengthOfSubsequences(i + 1, n, nums, q, sum + nums[i], len + 1);
}
// Choice 2: Exclude current element
maxLengthOfSubsequences(i + 1, n, nums, q, sum, len);
}
// Function to process queries and find the longest subsequence for each query
int[] answerQueries(int[] nums, int[] queries) {
// Store the size of nums array
int n = nums.length;
// Store the size of queries array
int m = queries.length;
// Answer array to store results
int[] answer = new int[m];
// Iterate over each query
for(int i = 0; i < m; ++i) {
// Initialize max_length to 0 for the current query
max_length = 0;
// Call recursive function to find max subsequence length
maxLengthOfSubsequences(0, n, nums, queries[i], 0, 0);
// Store the result for current query
answer[i] = max_length;
}
// Return the answer array
return answer;
}
}Longest Subsequence With Limited Sum solution in python
class Solution:
# Define the constructor to initialize instance variables
def __init__(self):
# Initialize max_length to 0
self.max_length = 0
# Define a recursive helper function to compute the longest valid subsequence
def maxLengthOfSubsequences(self, i: int, n: int, nums: List[int], q: int, sum_: int, length: int) -> None:
# Check if the current index i has reached or exceeded the length of nums
if i >= n:
# Update self.max_length with the maximum between current max_length and current length
self.max_length = max(self.max_length, length)
# Return from the function as there are no more elements to process
return
# If including nums[i] does not cause the sum to exceed q, then explore including it
if sum_ + nums[i] <= q:
# Recursively call the function including the current element (update sum and length)
self.maxLengthOfSubsequences(i + 1, n, nums, q, sum_ + nums[i], length + 1)
# Recursively call the function excluding the current element
self.maxLengthOfSubsequences(i + 1, n, nums, q, sum_, length)
# Define the main function answerQueries with the provided signature to process queries
def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
# Initialize an empty list to store the results for each query
result = []
# Compute the length of the nums list
n = len(nums)
# Loop over each query in the queries list
for q in queries:
# Reset max_length to 0 for the current query
self.max_length = 0
# Call the recursive helper function starting from index 0 with initial sum 0 and length 0
self.maxLengthOfSubsequences(0, n, nums, q, 0, 0)
# Append the computed max_length for this query to the result list
result.append(self.max_length)
# Return the list containing answers for all queries
return resultLongest Subsequence With Limited Sum solution in javascript
/**
* @param {number[]} nums
* @param {number[]} queries
* @return {number[]}
*/
var answerQueries = function(nums, queries) {
// Initialize an empty array to store results for each query
let result = [];
// Get the length of the nums array
let n = nums.length;
// Loop over each query in the queries array
for (let q of queries) {
// Initialize max_length for the current query to 0
let max_length = 0;
// Define a recursive helper function to compute the maximum valid subsequence length
function maxLengthOfSubsequences(i, sum, len) {
// If the index i is equal to or exceeds the length of nums, update max_length
if (i >= n) {
// Update max_length with the maximum of current max_length and len
max_length = Math.max(max_length, len);
// Return from the function as there are no more elements to process
return;
}
// If adding nums[i] to the current sum does not exceed q, explore including it
if (sum + nums[i] <= q) {
// Recursively call the function including the current element (update sum and len)
maxLengthOfSubsequences(i + 1, sum + nums[i], len + 1);
}
// Recursively call the function excluding the current element
maxLengthOfSubsequences(i + 1, sum, len);
}
// Start the recursive process from index 0 with initial sum 0 and length 0
maxLengthOfSubsequences(0, 0, 0);
// Append the computed max_length for the current query to the result array
result.push(max_length);
}
// Return the array containing the results for all queries
return result;
};Time Complexity: O(m×2n)
Recursive Function Complexity
The function maxLengthOfSubsequences(i, n, nums, q, sum, len) explores all subsequences using recursion. For each element, we have two choices:
- Include the element in the subsequence (if sum + nums[i] <= q).
- Exclude the element from the subsequence.
Since each element has two possibilities (included or not), the recursion tree grows exponentially with a branching factor of 2. This results in a time complexity of: O(2n )
where n is the size of nums.
Loop Over Queries
The function answerQueries() iterates over m queries, calling the recursive function maxLengthOfSubsequences() for each query.
Since the worst-case complexity of maxLengthOfSubsequences() is O(2n), and it is called m times, the total time complexity is: O(m×2n)
Conclusion
- Time Complexity: O(m×2n) → Exponential, impractical for large n (n>20).
Space Complexity: O(n)
Auxiliary Space Complexity
Extra memory used for computation
Recursion Stack Space
- The recursive function maxLengthOfSubsequences() makes two recursive calls for each index i in nums.
- The maximum depth of recursion is O(n), since in the worst case, we go through all elements one by one.
- Each recursive call adds a new stack frame, so the auxiliary space for recursion is: O(n)
Extra Variables
- The function uses a global variable max_length, which takes O(1) space.
- Other local variables (i, n, q, sum, len) are stored in the stack but are constant per function call, so their space complexity is O(1).
Hence auxiliary space complexity is: O(n)
Total Space Complexity
Includes input storage
Storage for Input and Output
- nums has O(n) space.
- queries has O(m) space.
- answer vector stores m integers, requiring O(m) space.
Thus, the total storage space is: O(n+m)
Better Approach
Intuition:
Now, to optimize this, let me ask you a simple question...
If you are given nums of size 5 and asked to choose 3 elements from nums such that the sum of these 3 elements is the minimum possible sum out of any 3 elements you choose from the array. What's your say on this?
You would definitely say that the minimum 3 values of the nums array will give the minimum possible sum of any combination of 3 elements in nums. And in fact, you are right.
Since we aim to maximize the length of the subsequence with a sum less than or equal to query[i], we should choose the smallest elements from nums to keep the sum as low as possible. If this minimum sum is not less than or equal to query[i], then no other combination will satisfy the condition either, as any other sum would be larger.
To achieve the smallest elements, we can sort our nums array. Because after sorting it would be easy to keep our sum of subsequence as low as possible. For example, if you need the minimum sum of length 3, then you can simply take the sum of the 3 elements in nums, as that sum would be the minimum.
This approach is somewhat related to the Longest Increasing Subsequence (LIS) problem, where we try to build the longest possible sequence such that every other element is greater than the previous element. However, instead of ensuring increasing order, our goal here is to maximize the length of the subsequence while keeping its sum within a given limit.
Reading this, you might have a doubt. You could think that sorting would change the order of the elements, and the sum we calculate from the sorted nums would no longer be the sum of a subsequence because a subsequence must maintain the original order!
Example:
Suppose nums = [4, 5, 3, 2, 1].
If we choose a subsequence like [5, 2, 1], we might worry that sorting will change the order, but we’re actually not concerned with the order of the elements in the subsequence. We only care about the sum.
Whether we pick the elements as [5, 2, 1], [2, 1, 5], or [1, 2, 5], all of these have the same sum of 8. Therefore, sorting the array won’t affect the sum of the subsequence, and it will not impact our final answer.
With this knowledge, it won't be wrong to say longest sum subarray. Because after sorting, we are concerned with the longest subarray we can achieve with a sum less than or equal to query[i].
Longest Subsequence With Limited Sum Solution
Initially, we sorted the nums array to make it easier to find the smallest elements.
Then, for each query, we check whether adding the current element nums[i] to our running sum keeps it within the limit set by query[i].
If the sum remains within the limit, we update our sum and increment the length, indicating that including nums[i] still satisfies the condition.
However, if adding nums[i] exceeds query[i], we stop the process and store the current length as the answer for that query. This ensures that we always select the longest possible subsequence whose sum does not exceed the given limit.
Longest Subsequence With Limited Sum example
Input: nums = [1, 2, 1, 5], queries = [2, 3, 4]
Output: [2, 2, 3]
Explanation: query[0] will have longest subsequence of length = 2, [1, 1], query[1] will also have longest subsequence of length =2 [1, 1] while query[2] has longest subsequence of length = 3 [1,2,1].
Step 1: Sorting nums
After sorting, nums becomes: [1, 1, 2, 5]
Step 2: Iterating Over Queries
We have three queries: [2, 3, 4].
Processing queries[0] = 2
- Initialize length = 0, sum = 0
- Iterate through nums:
- sum + nums[0] = 0 + 1 = 1 (≤ 2) → Add nums[0], length = 1
- sum + nums[1] = 1 + 1 = 2 (≤ 2) → Add nums[1], length = 2
- sum + nums[2] = 2 + 2 = 4 (> 2) → Stop
- Result for this query: answer[0] = 2
Processing queries[1] = 3
- Initialize length = 0, sum = 0
- Iterate through nums:
- sum + nums[0] = 0 + 1 = 1 (≤ 3) → Add nums[0], length = 1
- sum + nums[1] = 1 + 1 = 2 (≤ 3) → Add nums[1], length = 2
- sum + nums[2] = 2 + 2 = 4 (> 3) → Stop
- Result for this query: answer[1] = 2
Processing queries[2] = 4
- Initialize length = 0, sum = 0
- Iterate through nums:
- sum + nums[0] = 0 + 1 = 1 (≤ 4) → Add nums[0], length = 1
- sum + nums[1] = 1 + 1 = 2 (≤ 4) → Add nums[1], length = 2
- sum + nums[2] = 2 + 2 = 4 (≤ 4) → Add nums[2], length = 3
- sum + nums[3] = 4 + 5 = 9 (> 4) → Stop
- Result for this query: answer[2] = 3
Final Output: [2, 2, 3]
Steps to write code
Step 1: Sort the Array:
- Sorting nums in ascending order ensures that we pick the smallest elements first, maximizing the subsequence length.
Step 2: Iterate Over Queries:
- For each query value, find the longest subsequence whose sum is ≤ query value.
Step 3: Find the Maximum Length of a Valid Subsequence:
- Initialize sum = 0 and length = 0.
- Traverse through the sorted nums, adding elements to sum until it exceeds the query value.
Step 4: Store the Result for Each Query:
- Store the computed length in the answer array.
Return the Final Answer Array.
Better approach in All Languages
Longest Subsequence With Limited Sum solution in c++
class Solution {
public:
// Function to answer queries
vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {
// Get the size of nums and queries
int n = nums.size();
int m = queries.size();
// Sort the nums array
sort(nums.begin(), nums.end());
// Vector to store the result for each query
vector<int> answer(m);
// Loop through each query
for(int i = 0; i < m; ++i) {
// Variables to calculate the number of elements that sum up to the query
int length = 0;
int sum = 0;
// Loop through the nums array
for(int j = 0; j < n; ++j) {
// If adding the current element doesn't exceed the query, include it
if(sum + nums[j] <= queries[i]) {
sum += nums[j];
length++;
}
}
// Store the result for the current query
answer[i] = length;
}
// Return the results
return answer;
}
};Longest Subsequence With Limited Sum solution in java
class Solution {
// Function to answer queries
public int[] answerQueries(int[] nums, int[] queries) {
// Sort the nums array
Arrays.sort(nums);
// Array to store the result for each query
int[] answer = new int[queries.length];
// Loop through each query
for (int i = 0; i < queries.length; ++i) {
// Variables to calculate the number of elements that sum up to the query
int length = 0;
int sum = 0;
// Loop through the nums array
for (int num : nums) {
// If adding the current element doesn't exceed the query, include it
if (sum + num <= queries[i]) {
sum += num;
length++;
}
}
// Store the result for the current query
answer[i] = length;
}
// Return the results
return answer;
}
};Longest Subsequence With Limited Sum solution in python
class Solution:
# Function to answer queries
def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
# Sort the nums array
nums.sort()
# List to store the result for each query
answer = []
# Loop through each query
for query in queries:
# Variables to calculate the number of elements that sum up to the query
length = 0
sum = 0
# Loop through the nums array
for num in nums:
# If adding the current element doesn't exceed the query, include it
if sum + num <= query:
sum += num
length += 1
# Append the result for the current query
answer.append(length)
# Return the results
return answerLongest Subsequence With Limited Sum solution in javascript
/**
* @param {number[]} nums
* @param {number[]} queries
* @return {number[]}
*/
var answerQueries = function(nums, queries) {
// Sort the nums array
nums.sort((a, b) => a - b);
// Array to store the result for each query
let answer = [];
// Loop through each query
for (let query of queries) {
// Variables to calculate the number of elements that sum up to the query
let length = 0;
let sum = 0;
// Loop through the nums array
for (let num of nums) {
// If adding the current element doesn't exceed the query, include it
if (sum + num <= query) {
sum += num;
length++;
}
}
// Push the result for the current query
answer.push(length);
}
// Return the results
return answer;
}Longest Subsequence With Limited Sum Complexity Analysis
Time Complexity: O(m×n)
The given function follows these steps:
Sorting the nums array
- Sorting takes O(n log n), where n is the size of nums.
Processing Each Query
- For each query, we iterate over nums to compute the longest subsequence.
- The worst-case scenario is iterating through all n elements.
- There are m queries, so the total complexity for this part is O(m × n).
Overall Complexity
- Sorting: O(nlogn)
- Processing queries: O(m×n)
- Total Complexity: O(nlogn+m×n) reduces to O(m×n)
Space Complexity: O(m)
Auxiliary Space Complexity:
Extra space used by the algorithm excluding input storage.
- Sorting Overhead:
- Sorting nums is in-place, so it does not consume extra space.
- If an external sorting algorithm is used, the worst-case auxiliary space would be O(n).
- Result Storage (answer vector):
- We store results for m queries → O(m) space.
- Loop Variables (length, sum, etc.):
- Uses a constant amount of space O(1).
- Total Auxiliary Space Complexity: O(m)
Total Space Complexity:
Total memory used, including input storage.
- Input Arrays:
- nums takes O(n) space.
- queries takes O(m) space.
- The answer array takes O(m) space.
Total Space Complexity: O(n+m)
Is the brute force approach feasible?
The complexity of the solution is O(m×n). Here n, m <= 1000. this means O(m×n) does maximum 106 operations.
This is well within the time limits of most competitive programming environments, which typically allow around 1-2 seconds for execution.
In such environments, it is common for problems to handle up to 10⁶ operations within these limits.
Most competitive programming platforms, like LeetCode, allow up to 10⁶ operations per test case, meaning your solution should be able to handle this number of operations within the time limits. When multiple test cases are involved, the total number of operations can go up to 10⁸.
Hence our solution is feasible. But still let's see if we can optimize this.
Optimal Approach
Intuition:
The current complexity of our solution is O(m×n), where m is the number of queries and n is the size of the nums array. We iterate over the queries to find answers for each query. For each query, we iterate over nums, which gives us the time complexity of m × n.
Now, think about which loop we can optimize?...
Since we need to find the answer for each query, we must iterate over queries to get answers for all of them. Hence, we can optimize the m here, but let's see how we can optimize the inner loop that iterates over nums.
Let's see what exactly we are doing while iterating over nums...
We are keeping track of the sum of values from indexes 0 to i to check if the sum is less than or equal to queries[i]. Secondly, we are keeping track of the length of all values a valid subarray from index 0 to i giving a sum less than or equal to queries[i].
If I ask you to give the sum of elements from index 0 to i in O(1) inside the loop of queries, here’s how you can do it:
Before iterating over the queries, we perform some precomputation. We initialize an array of size n, where each index i stores the sum of the elements of nums from index 0 to i. This can be done with a simple loop:
- Initialize the first element of the array to be the first element of nums.
- For every other element, add nums[i] to the value stored at index i-1 in the array.
This way, by adding nums[i] to the sum of elements from 0 to i-1, we get the sum of elements from 0 to i. This technique is known as prefix sum. The advantage is that once the prefix_sum array is computed, you can access the sum of elements from index 0 to i in O(1) time, making it much faster inside the query loop.
You can learn more about the prefix sum approach here
Now, as we know the structure until some index j, the prefix_sum[j] will be valid, meaning prefix_sum[j] will be less than or equal to query[i], but all the prefix_sum values from index j+1 to n-1 will give prefix_sum[j] greater than queries[i]. Hence now we aim to find this index j such that this index is the maximum index where prefix_sum[j] is valid.
How to maximise value j such that prefix_sum[j] is less than or equal to queries[i] without iterating over prefix_sum?
To do this, let’s consider a middle index (mid) from the prefix_sum. The value of prefix_sum[mid] will either be greater than queries[i] or less than or equal to queries[i]. Based on this, we can create a strategy to search more efficiently for the index j where the sum condition holds. Let's address these two cases:
Case 1: prefix_sum[mid] is less than or equal to queries[i]
In this case, we know that the index mid might be the j we are looking for, but we still need to check the right side of the mid to see if we can find a larger valid value that will still be less than or equal to queries[i]. This is because, in a sorted array, larger sums are found as we move to the right, so there may be a larger valid subsequence that satisfies the condition.
Example
For example, let's assume:
- prefix_sum = [1, 3, 6, 8, 15]
- queries[i] = 9
When we check the middle index (mid = 2), we find prefix_sum[mid] = 6, which is less than queries[i] = 9. So, we know that mid is too small, but prefix_sum[mid+1] = 8 might still be a valid candidate. Thus, we move right to see if there is a valid subsequence whose sum is less than or equal to queries[i].
Case 2: prefix_sum[mid] is greater than or equal to queries[i]
In this case, we know that the value at index mid may be too large, and we need to check the left side of mid to see if there’s a smaller subsequence that still satisfies the condition. This is because the sums are non-decreasing in a sorted prefix sum array, and we are trying to find the largest subsequence length such that the sum is less than or equal to queries[i].
Example
For example, let’s assume:
- prefix_sum = [1, 3, 6, 10, 15]
- queries[i] = 3
When we check mid = 2, we find that prefix_sum[mid] = 6, which is less than queries[i] = 3. We know that the mid is too large, so we check towards the left of the mid in search of j since all elements towards the right will be greater than or equal to queries[i].
The strategy here is a binary search approach, where you adjust the range based on whether prefix_sum[mid] is greater than or less than queries[i]. By narrowing down the range in each step, you can efficiently find the longest subsequence whose sum is less than or equal to queries[i].
To learn more about binary search, look at the article below.
Longest Subsequence With Limited Sum Algorithm
Initially, we process the nums array.
- Sort the nums array.
- Build a prefix_sum array out of the nums array.
After processing the nums, we iterate over queries and apply binary search to find a valid value j such that j is the maximum valid index where prefix_sum[j] is less than or equal to queries[i].
After we find j, all we need is the length of the value from index 0 to j. The length is simply j+1.
We store this value in our answer array, and finally, we return the answer at the end.
Animation to better understand the Optimal Approach
Longest Subsequence With Limited Sum example
Input: nums = [1, 2, 1, 5], queries = [2, 3, 4]
Output: [2, 2, 3]
Explanation: query[0] will have longest subsequence of length = 2, [1, 1], query[1] will also have longest subsequence of length =2 [1, 1] while query[2] has longest subsequence of length = 3 [1,2,1].
Input:
- nums = [1, 2, 1, 5]
- queries = [2, 3, 4]
Step 1: Sort the nums array
- Sorting nums results: nums = [1, 1, 2, 5]
Step 2: Compute the Prefix Sum Array
The prefix sum array (prefix_sum) is calculated as follows:
- Start with the first element of nums: prefix_sum[0] = nums[0] = 1
- For the next element, sum the previous prefix and the current element: prefix_sum[1] = prefix_sum[0] + nums[1] = 1 + 1 = 2
- For the next element: prefix_sum[2] = prefix_sum[1] + nums[2] = 2 + 2 = 4
- For the next element: prefix_sum[3] = prefix_sum[2] + nums[3] = 4 + 5 = 9
Final prefix_sum: prefix_sum = [1, 2, 4, 9]
Step 3: Process Each Query
Query 1: queries[0] = 2
We perform binary search to find the largest j such that prefix_sum[j] <= queries[0] (i.e., 2).
- Start with low = 0, high = 3, and j = -1 (initial value).
- First, calculate mid = (low + high) / 2 = (0 + 3) / 2 = 1:
- prefix_sum[1] = 2, which is equal to the query (2).
- Set j = 1 and update low = mid + 1 = 2.
- Now, calculate mid = (2 + 3) / 2 = 2:
- prefix_sum[2] = 4, which is greater than the query.
- Update high = mid - 1 = 1.
- At this point, binary search terminates, and we have j = 1. Since j != -1, the result for this query is j + 1 = 1 + 1 = 2.
Query 2: queries[1] = 3
We perform binary search to find the largest j such that prefix_sum[j] <= queries[1] (i.e., 3).
- Start with low = 0, high = 3, and j = -1.
- First, calculate mid = (low + high) / 2 = (0 + 3) / 2 = 1:
- prefix_sum[1] = 2, which is less than the query (3).
- Set j = 1 and update low = mid + 1 = 2.
- Now, calculate mid = (2 + 3) / 2 = 2:
- prefix_sum[2] = 4, which is greater than the query.
- Update high = mid - 1 = 1.
- At this point, binary search terminates, and we have j = 1. Since j != -1, the result for this query is j + 1 = 1 + 1 = 2.
Query 3: queries[2] = 4
We perform binary search to find the largest j such that prefix_sum[j] <= queries[2] (i.e., 4).
- Start with low = 0, high = 3, and j = -1.
- First, calculate mid = (low + high) / 2 = (0 + 3) / 2 = 1:
- prefix_sum[1] = 2, which is less than the query (4).
- Set j = 1 and update low = mid + 1 = 2.
- Now, calculate mid = (2 + 3) / 2 = 2:
- prefix_sum[2] = 4, which is equal to the query.
- Set j = 2 and update low = mid + 1 = 3.
- Now, calculate mid = (3 + 3) / 2 = 3:
- prefix_sum[3] = 9, which is greater than the query.
- Update high = mid - 1 = 2.
- At this point, binary search terminates, and we have j = 2. Since j != -1, the result for this query is j + 1 = 2 + 1 = 3.
Final Output:
After processing all the queries, the results are: [2, 2, 3]
Steps to write code
Step 1: Sort the nums Array
- Use sort() to sort the nums array in non-decreasing order. This will help in calculating the prefix sums in an efficient manner.
Step 2: Calculate the Prefix Sum Array
- Initialize a prefix_sum array of the same size as nums.
- The first element of prefix_sum will be the first element of nums. Then, iterate over the array and fill in the cumulative sums.
Step 3: Prepare the Result Array
- Create a vector answer to store the results for each query.
Step 4: Binary Search for Each Query
- For each query, initialize low = 0 and high = n - 1.
- Perform binary search to find the largest index j such that prefix_sum[j] <= queries[i].
- Use a while loop to perform the binary search and update low, high, and j accordingly.
Step 5: Store the Result for Each Query
- After the binary search, check if j != -1. If true, store j + 1 as the result for the current query; otherwise, store 0.
Step 6: Return the Final Answer
- After processing all queries, return the answer array containing the results for all queries
Optimal Approach in All Languages
Longest Subsequence With Limited Sum solution in C++
class Solution {
public:
// Function to answer queries
vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {
// Get the size of nums and queries
int n = nums.size();
int m = queries.size();
// Sort the nums array
sort(nums.begin(), nums.end());
// Create a prefix sum array to store cumulative sums
vector<int> prefix_sum(n);
prefix_sum[0] = nums[0];
// Calculate the prefix sums
for(int i = 1; i < n; ++i) {
prefix_sum[i] = prefix_sum[i - 1] + nums[i];
}
// Vector to store the result for each query
vector<int> answer(m);
// Loop through each query
for(int i = 0; i < m; ++i) {
// Binary search to find the largest j such that prefix_sum[j] <= query
int j = -1;
int low = 0, high = n - 1;
while(low <= high) {
int mid = (low + high) / 2;
if(prefix_sum[mid] <= queries[i]) {
j = mid;
low = mid + 1;
}
else {
high = mid - 1;
}
}
// Store the result for the current query
answer[i] = j == -1 ? 0 : j + 1;
}
// Return the results
return answer;
}
};Longest Subsequence With Limited Sum solution in java
class Solution {
// Function to answer queries
public int[] answerQueries(int[] nums, int[] queries) {
// Sort the nums array
Arrays.sort(nums);
// Create a prefix sum array to store cumulative sums
int n = nums.length;
int[] prefix_sum = new int[n];
prefix_sum[0] = nums[0];
// Calculate the prefix sums
for (int i = 1; i < n; ++i) {
prefix_sum[i] = prefix_sum[i - 1] + nums[i];
}
// Array to store the result for each query
int[] answer = new int[queries.length];
// Loop through each query
for (int i = 0; i < queries.length; ++i) {
// Binary search to find the largest j such that prefix_sum[j] <= query
int low = 0, high = n - 1;
int j = -1;
while (low <= high) {
int mid = (low + high) / 2;
if (prefix_sum[mid] <= queries[i]) {
j = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
// Store the result for the current query
answer[i] = j == -1 ? 0 : j + 1;
}
// Return the results
return answer;
}
}Longest Subsequence With Limited Sum solution in python
class Solution:
# Function to answer queries
def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
# Sort the nums array
nums.sort()
# Create a prefix sum array to store cumulative sums
prefix_sum = [0] * len(nums)
prefix_sum[0] = nums[0]
# Calculate the prefix sums
for i in range(1, len(nums)):
prefix_sum[i] = prefix_sum[i - 1] + nums[i]
# List to store the result for each query
answer = []
# Loop through each query
for query in queries:
# Binary search to find the largest j such that prefix_sum[j] <= query
low, high = 0, len(nums) - 1
j = -1
while low <= high:
mid = (low + high) // 2
if prefix_sum[mid] <= query:
j = mid
low = mid + 1
else:
high = mid - 1
# Append the result for the current query
answer.append(j + 1 if j != -1 else 0)
# Return the results
return answerLongest Subsequence With Limited Sum solution in javascript
/**
* @param {number[]} nums
* @param {number[]} queries
* @return {number[]}
*/
var answerQueries = function(nums, queries) {
// Sort the nums array
nums.sort((a, b) => a - b);
// Create a prefix sum array to store cumulative sums
const prefix_sum = [];
prefix_sum[0] = nums[0];
// Calculate the prefix sums
for (let i = 1; i < nums.length; i++) {
prefix_sum[i] = prefix_sum[i - 1] + nums[i];
}
// Array to store the result for each query
const answer = [];
// Loop through each query
for (let query of queries) {
// Binary search to find the largest j such that prefix_sum[j] <= query
let low = 0, high = nums.length - 1;
let j = -1;
while (low <= high) {
const mid = Math.floor((low + high) / 2);
if (prefix_sum[mid] <= query) {
j = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
// Push the result for the current query
answer.push(j === -1 ? 0 : j + 1);
}
// Return the results
return answer;
}Longest Subsequence With Limited Sum Complexity Analysis
Time Complexity: O((n+m)logn)
Sorting the nums Array
- Sorting the nums array takes O(nlogn) time, where n is the size of the nums array.
- Time Complexity: O(nlogn)
Calculating the Prefix Sum Array
- Calculating the prefix sum array involves a single pass through the nums array, which takes O(n) time.
- Time Complexity: O(n)
Binary Search for Each Query
- For each query, a binary search is performed on the prefix_sum array. The binary search operates in O(logn) time, where n is the size of the prefix_sum array.
- Since there are m queries, the total time for processing all queries is O(mlogn).
Breaking It Down
- At the beginning: The search space has n elements.
- After 1st iteration: The search space is reduced to n/2.
- After 2nd iteration: The search space is n/4.
- After k iterations: The search space becomes n / 2k.
The search ends when only one element remains, which happens when: n/2k = 1
Taking log base 2 on both sides: k=log2(n)
Thus, binary search runs in O(log n) time complexity.
- Time Complexity for Queries: O(mlogn)
Overall Time Complexity
- The overall time complexity is the sum of the time complexities for sorting the array, computing the prefix sum, and processing the queries: O(nlogn)+O(n)+O(mlogn)
- Since O(nlogn) dominates O(n), the final overall time complexity is: O(nlogn+mlogn)
- Final Time Complexity: O((n+m)logn)
Space Complexity: O(n+m)
Auxiliary Space Complexity
Auxiliary space refers to the extra space used by the algorithm that is not part of the input.
- The only additional space used (apart from the input data) is:
- The prefix_sum array: This stores the cumulative sums of the nums array, which takes O(n) space.
- The answer array: This stores the results for each query, which takes O(m) space.
Thus, the total auxiliary space used is:
O(n)+O(m)=O(n+m)
Total Space Complexity
Total space complexity considers both the input data and the auxiliary space.
- Input space:
- The nums array takes O(n) space.
- The queries array takes O(m) space.
- Auxiliary space:
- The prefix_sum array takes O(n) space.
- The answer array takes O(m) space.
Thus, the total space complexity is:
O(n)+O(m) (for input arrays)+O(n)+O(m) (for auxiliary arrays)=O(n+m)
Final Space Complexity:
- Auxiliary Space Complexity: O(n+m)
- Total Space Complexity: O(n+m)
Similar Problems
Now we have successfully tackled this problem, let's try these similar problems:-
Given the array nums, for each nums[i] find out how many numbers in the array are smaller than it. That is, for each nums[i] you have to count the number of valid j's such that j != i and nums[j] < nums[i].
Return the answer in an array.
You are given two positive integer arrays spells and potions, of length n and m respectively, where spells[i] represents the strength of the ith spell and potions[j] represents the strength of the jth potion.
You are also given an integer success. A spell and potion pair is considered successful if the product of their strengths is at least success.
Return an integer array pairs of length n where pairs[i] is the number of potions that will form a successful pair with the ith spell.