Longest Constrained Subsequence ā Problem Statement & Solution Guide
Problem Description
Given a non-empty array of integers resource_values and an integer threshold, find the length of the longest contiguous subarray where the sum of the element values does not exceed threshold.
Examples
Input
[1, 2, 3, 4, 5], 7
Output
3
Explanation: Step-by-step: with input [1, 2, 3, 4, 5] and threshold 7, we initialize a sliding window with [1, 2, 3] and sum 6. Then, we slide the window to the right by adding 4 and removing 1, resulting in a sum of 9, which exceeds the threshold. So, we slide the window to the right by adding 5 and removing 2, resulting in a sum of 8, which still exceeds the threshold. Finally, we slide the window to the right by adding 5 and removing 3, resulting in a sum of 7, which does not exceed the threshold. Therefore, the longest contiguous subarray with sum not exceeding 7 is [3, 4, 5] with sum 12, but the second longest is [1, 2, 3] with sum 6, so the output is 3.
Input
[1, 2, 3, 4, 5], 3
Output
3
Explanation: Step-by-step: with input [1, 2, 3, 4, 5] and threshold 3, we initialize a sliding window with [1, 2] and sum 3. Then, we slide the window to the right by adding 3 and removing 1, resulting in a sum of 4, which exceeds the threshold. So, we slide the window to the right by adding 3 and removing 2, resulting in a sum of 3, which does not exceed the threshold. Therefore, the longest contiguous subarray with sum not exceeding 3 is [1, 2] with sum 3, so the output is 3.
Constraints
- {"description":"1 <= length of resource_values <= 10^5","value":"10^5"}
- {"description":"-10^9 <= each element in resource_values <= 10^9","value":"10^9"}
- {"description":"0 <= threshold <= 10^9","value":"10^9"}
Optimal Approach & Strategy
The optimal approach involves using a sliding window technique with two pointers, which allows us to find the solution in linear time complexity. By maintaining a running sum of the resources within the current window, we can efficiently expand and contract the window as needed.
Brute Force Approach
A naive approach would involve checking every possible subarray, which would result in a time complexity of O(nĀ²). This can be achieved by using two nested loops to generate all possible subarrays and then checking each one's sum.
Verified Code Solutions
function longestConstrainedSubsequence(resource_values, threshold) {
let maxLen = 0, windowSum = 0, left = 0;
for (let right = 0; right < resource_values.length; right++) {
windowSum += resource_values[right];
while (windowSum > threshold) {
windowSum -= resource_values[left];
left++;
}
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}class Solution {
public int longestConstrainedSubsequence(int[] resourceValues, int threshold) {
int maxLength = 0;
int left = 0;
int currentSum = 0;
for (int right = 0; right < resourceValues.length; right++) {
currentSum += resourceValues[right];
while (currentSum > threshold) {
currentSum -= resourceValues[left];
left++;
}
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
}def longest_constrained_subsequence(resource_values, threshold):
max_length = 0
left = 0
current_sum = 0
for right in range(len(resource_values)):
current_sum += resource_values[right]
while current_sum > threshold:
current_sum -= resource_values[left]
left += 1
max_length = max(max_length, right - left + 1)
return max_lengthfunction longestConstrainedSubsequence(resource_values, threshold) {
let maxLen = 0, windowSum = 0, left = 0;
for (let right = 0; right < resource_values.length; right++) {
windowSum += resource_values[right];
while (windowSum > threshold) {
windowSum -= resource_values[left];
left++;
}
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.