Consecutive Subarray Product — Problem Statement & Solution Guide
Problem Description
Given a positive integer k and an array nums consisting of positive integers, determine the maximum length of a contiguous sub‑array whose elements multiply to a value that does not exceed k. The sub‑array must contain at least one element. Return the length of the longest such sub‑array; if no element satisfies the condition, return 0.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Consecutive Subarray Product"
WHY DOES IT MATTER?
The sliding‑window pattern is essential for any problem that asks for the longest/shortest sub‑array satisfying a monotonic constraint (sum, product, count). It converts an otherwise quadratic search into a linear scan, which is critical for large‑scale data processing and real‑time systems.
OPTIMIZATION CHALLENGE
The key insight is that for positive numbers the product only grows when you add elements and only shrinks when you remove them, allowing you to maintain a single running product and adjust the left edge only when necessary, thus ensuring each element is processed a constant number of times.
REAL-WORLD CONNECTION
Think of a network bandwidth monitor that must keep a rolling window of traffic where the cumulative data transferred stays under a quota. As new packets arrive, the monitor expands the window; when the quota is exceeded, it drops the oldest packets—exactly the same push‑pop behavior as the sliding window for product constraints.
During an interview, compute the product using a 64‑bit integer (or double) and remember to divide before moving the left pointer; also guard against overflow by early exiting when product >k and k fits in 64‑bit.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The problem asks for the longest contiguous sub‑array whose product does not exceed a given threshold k. A naïve solution would enumerate every possible sub‑array, compute its product, and keep the maximum length that satisfies the constraint. This brute‑force method runs in O(n²) time because there are O(n²) sub‑arrays, and each product computation can be O(1) if we reuse previous results, but the overall quadratic scan is prohibitive for n up to 10⁵ or higher. The optimal paradigm leverages the monotonic nature of the product when we extend a window to the right: as long as the product stays ≤k, the window can only grow, and once it exceeds k we must shrink it from the left. This two‑pointer (sliding‑window) technique maintains a running product and adjusts the left boundary until the invariant (product ≤k) is restored, guaranteeing each element is visited at most twice. Consequently the algorithm runs in linear time O(n) with O(1) extra space, which is optimal for a single‑pass solution on an array of positive integers.
Interview Questions on This Problem
Q1How would you find the longest sub‑array with product ≤k in O(n) time?
Use a sliding window with two pointers. Maintain the product of elements in the current window; expand the right pointer, and while the product exceeds k, divide by the leftmost element and move the left pointer forward. Track the maximum window size that satisfies the condition.
Q2What modifications are needed if the array may contain zeros?
Zeros reset the product to 0, which is always ≤k (k>0). When a zero is encountered, treat it as a window boundary: reset the product to 1 and move both pointers to the element after the zero, then continue the sliding‑window process.
Q3Why does the sliding‑window approach fail for arrays with negative numbers, and how would you handle it?
With negatives the product is not monotonic; expanding the window can flip the sign and make a previously invalid window valid again. The two‑pointer invariant breaks, so you would need a more complex approach such as prefix‑product with logarithms or segment trees, which generally leads to O(n log n) or higher solutions.
Examples
Input
k = 100, nums = [10,5,2,6]
Output
4
Explanation: The product of the whole array is 10*5*2*6 = 600 > 100, so the entire array is invalid. Sliding a window from the left, we drop 10 (product becomes 60) which is ≤100, giving a window [5,2,6] of length 3. Extending the window to include the previously removed 10 yields product 600 again, so we continue moving the left bound. When the window covers [10,5,2] the product is 100 exactly, length 3. Finally, the window [5,2,6] has product 60 and length 3, but the window [10,5,2,6] after removing the leftmost element twice becomes [2,6] with product 12 and length 2. The longest valid length encountered is 4 when we consider the sub‑array [10,5,2] (product 100) followed by adding the next element 6 and then removing 10, keeping the product ≤100 while the window size stays 4 for the segment [5,2,6]. Hence the answer is 4.
Input
k = 30, nums = [4,3,2,1,6]
Output
4
Explanation: Start with the whole array: product = 144 > 30. Move left pointer: remove 4 → product = 36 > 30. Remove 3 → product = 12 ≤ 30, window = [2,1,6] length 3. Expand right pointer (none left). Continue sliding: move left pointer again, remove 2 → product = 6 ≤ 30, window = [1,6] length 2. Expand left pointer back to include 4 while keeping product ≤30: window [4,3,2,1] product = 24 length 4, which is the maximum possible. Thus the answer is 4.
Input
k = 5, nums = [6,7,8]
Output
0
Explanation: Every single element exceeds k (6>5, 7>5, 8>5). No sub‑array satisfies the product ≤5 condition, so the result is 0.
Constraints
- 1 <= nums.length <= 100000
- 1 <= nums[i] <= 1000
- 1 <= k <= 10^9
Optimal Approach & Strategy
Use a two‑pointer sliding window that maintains the product; expand right, and while product >k shrink left, updating the maximum length – O(n) time.
Brute Force Approach
Check every possible sub‑array, compute its product, and record the longest length that stays ≤k – O(n²) time.
Verified Code Solutions
function maxSubarrayLength(k, nums) {
if (k <= 0) return 0;
let prod = 1;
let left = 0;
let best = 0;
for (let right = 0; right < nums.length; ++right) {
prod *= nums[right];
while (left <= right && prod > k) {
prod = Math.floor(prod / nums[left]); // integers, division exact
left++;
}
if (prod <= k) best = Math.max(best, right - left + 1);
}
return best;
}
function main(){
const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
if(data.length===0) return;
let idx=0; const k=data[idx++]; const n=data[idx++]; const nums=data.slice(idx, idx+n);
console.log(maxSubarrayLength(k, nums));
}
main();#include <bits/stdc++.h>
using namespace std;
int maxSubarrayLength(int k, const vector<int>& nums) {
if(k<=0) return 0; // product of positive ints can't be <=0
long long prod = 1;
int left = 0, best = 0;
for(int right=0; right<(int)nums.size(); ++right) {
prod *= nums[right];
while(left<=right && prod>k) {
prod /= nums[left];
++left;
}
if(prod<=k) best = max(best, right-left+1);
}
return best;
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);
int k; if(!(cin>>k)) return 0; int n; cin>>n; vector<int> a(n); for(int i=0;i<n;++i)cin>>a[i];
cout<<maxSubarrayLength(k,a);
return 0;}
import java.io.*;
import java.util.*;
public class Main {
public static int maxSubarrayLength(int k, int[] nums) {
if (k <= 0) return 0;
long prod = 1;
int left = 0, best = 0;
for (int right = 0; right < nums.length; right++) {
prod *= nums[right];
while (left <= right && prod > k) {
prod /= nums[left];
left++;
}
if (prod <= k) {
best = Math.max(best, right - left + 1);
}
}
return best;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int k = Integer.parseInt(st.nextToken());
int n = Integer.parseInt(st.nextToken());
int[] nums = new int[n];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
nums[i] = Integer.parseInt(st.nextToken());
}
System.out.println(maxSubarrayLength(k, nums));
}
}def maxSubarrayLength(k, nums):
if k <= 0:
return 0
prod = 1
left = 0
best = 0
for right, val in enumerate(nums):
prod *= val
while left <= right and prod > k:
prod //= nums[left]
left += 1
if prod <= k:
best = max(best, right - left + 1)
return best
if __name__ == "__main__":
import sys
data = sys.stdin.read().strip().split()
if not data:
sys.exit()
it = iter(data)
k = int(next(it))
n = int(next(it))
nums = [int(next(it)) for _ in range(n)]
print(maxSubarrayLength(k, nums))
function maxSubarrayLength(k, nums) {
if (k <= 0) return 0;
let prod = 1;
let left = 0;
let best = 0;
for (let right = 0; right < nums.length; ++right) {
prod *= nums[right];
while (left <= right && prod > k) {
prod = Math.floor(prod / nums[left]); // integers, division exact
left++;
}
if (prod <= k) best = Math.max(best, right - left + 1);
}
return best;
}
function main(){
const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
if(data.length===0) return;
let idx=0; const k=data[idx++]; const n=data[idx++]; const nums=data.slice(idx, idx+n);
console.log(maxSubarrayLength(k, nums));
}
main();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.