Bounded Subarray Length — Problem Statement & Solution Guide
Problem Description
Given a sequence of integers values and an integer threshold, determine the maximum length of a contiguous subsequence within values such that the product of its elements does not exceed threshold. If the input array is empty, return 0.
Examples
Input
[10, 5, 2, 6], 100
Output
2
Explanation: Step-by-step: with input [10, 5, 2, 6] and threshold 100, we start with the first element 10. The product of the subarray [10] is 10, which does not exceed the threshold. Then we consider the subarray [10, 5], the product of which is 50, still not exceeding the threshold. However, adding the next element 2 to form [10, 5, 2] results in a product of 100, exactly at the threshold. Adding one more element would exceed the threshold. Thus, the maximum length of a contiguous subsequence without exceeding the threshold is 2.
Input
[1, 2, 3, 4], 10
Output
3
Explanation: Step-by-step: with input [1, 2, 3, 4] and threshold 10, we consider the subarrays starting from the first element. The subarray [1, 2, 3] has a product of 6, which does not exceed the threshold. However, adding the next element 4 to form [1, 2, 3, 4] results in a product of 24, which exceeds the threshold. Thus, the maximum length of a contiguous subsequence without exceeding the threshold is 3.
Constraints
- 1 ≤ array size ≤ 10^5
- 1 ≤ array elements ≤ 10^3
- 1 ≤ k ≤ 10^6
- Array may contain duplicate elements
Optimal Approach & Strategy
The optimized approach utilizes a sliding window technique, maintaining a running product of elements within the window and adjusting the window boundaries as necessary to keep the product within the given limit, achieving a time complexity of O(n).
Brute Force Approach
A brute-force approach involves checking every possible subarray and calculating the product of its elements, resulting in a time complexity of O(n²). This is inefficient for large inputs. The naive approach would iterate through all possible subarrays, leading to the same high time complexity.
Verified Code Solutions
function solution(values, threshold) { let maxLen = 0; for (let i = 0; i < values.length; i++) { let prod = 1; for (let j = i; j < values.length; j++) { prod *= values[j]; if (prod > threshold) break; maxLen = Math.max(maxLen, j - i + 1); } } return maxLen; }class Solution { public: int solution(vector<int>& values, int threshold) { int maxLen = 0; for (int i = 0; i < values.size(); i++) { long long prod = 1; for (int j = i; j < values.size(); j++) { prod *= values[j]; if (prod > threshold) break; maxLen = max(maxLen, j - i + 1); } } return maxLen; } }class Solution { public int solution(int[] values, int threshold) { int maxLen = 0; for (int i = 0; i < values.length; i++) { long prod = 1; for (int j = i; j < values.length; j++) { prod *= values[j]; if (prod > threshold) break; maxLen = Math.max(maxLen, j - i + 1); } } return maxLen; } }def solution(values, threshold): max_len = 0; for i in range(len(values)): prod = 1; for j in range(i, len(values)): prod *= values[j]; if prod > threshold: break; max_len = max(max_len, j - i + 1); return max_lenfunction solution(values, threshold) { let maxLen = 0; for (let i = 0; i < values.length; i++) { let prod = 1; for (let j = i; j < values.length; j++) { prod *= values[j]; if (prod > threshold) break; maxLen = Math.max(maxLen, j - i + 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.