Sliding Window — Subarray Product Less Than K
↗ LeetCode: Subarray Product Less Than K · Medium · pattern chapter →
Given a positive-int array nums and integer k, return the number of contiguous subarrays whose product is strictly less than k.
Example 1 — nums = [10,5,2,6], k = 100 → 8 (subarrays: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]) Example 2 — nums = [1,2,3], k = 0 → 0 (no positive product can be < 0) Example 3 — nums = [1,1,1], k = 2 → 6
Constraints — 1 ≤ n ≤ 3 · 10⁴; 1 ≤ nums[i] ≤ 1000; 0 ≤ k ≤ 10⁶. All values positive.
⏱️Interview timer00:00
Approach 1 — Every subarray
Intuition. For each [i, j], compute product; if < k, increment.
int numSubarrayProductLessThanKBrute(int[] nums, int k) {
int n = nums.length, count = 0;
for (int i = 0; i < n; i++) {
long prod = 1;
for (int j = i; j < n; j++) {
prod *= nums[j];
if (prod < k) count++;
else break;
}
}
return count;
}2
3
4
5
6
7
8
9
10
11
12
Complexity — Time O(n²); Space O(1).
Approach 2 — Sliding window with running product
Insight from brute. Products are monotone with positive values. Extend right; shrink left while prod ≥ k. Every subarray ending at right with left ∈ [currLeft, right] contributes (right - left + 1) new subarrays.
Trap — Early-return k ≤ 1: no product of positives is < 1.
int numSubarrayProductLessThanK(int[] nums, int k) {
if (k <= 1) return 0;
long prod = 1;
int count = 0, left = 0;
for (int right = 0; right < nums.length; right++) {
prod *= nums[right];
while (prod >= k) prod /= nums[left++];
count += right - left + 1;
}
return count;
}2
3
4
5
6
7
8
9
10
11
Complexity — Time O(n) — each index enters/leaves once; Space O(1).
Approach 3 — Prefix log-sum + binary search (interview polish)
Insight from sliding. Log-transforms products into sums: log(prod) = Σ log(nums[i]). Now the problem becomes "count sublists with prefix-log-sum difference < log k" — solvable via binary search on the prefix array. Rarely needed in practice, but shows the sum-log-product bridge.
Complexity — Time O(n log n); Space O(n). Suboptimal — the sliding window wins.
Try it yourself
Complexity summary
| Approach | Time | Space | Interview grade |
|---|---|---|---|
| Every subarray | O(n²) | O(1) | baseline |
| Sliding window | O(n) | O(1) | expected optimum |
| Log + prefix + BS | O(n log n) | O(n) | curiosity — sum-log-product bridge |
When to use which
- Standard answer → sliding window.
- "What if nums[i] can be 0?" → sliding breaks (0 zeros the product); split by zeros or use the log-sum + BS approach with
log(0) = -∞. - "What if nums[i] can be negative?" → both products and logs break; needs sign-tracking (see Maximum Product Subarray).
- "Return the subarrays themselves" → enumerate during the slide; loses the compact O(n) counting.
Related problems
- Maximum Product Subarray — signed variant
- Binary Subarrays With Sum — sibling with
atMosttrick - Count Number of Nice Subarrays — sibling
- Subarrays with K Different Integers