The challenge
Count nonempty contiguous subarrays whose product is strictly smaller than k.
1 ≤ nums[i] ≤ 10⁶; 0 ≤ k ≤ 10⁹. Empty input returns 0.
Example
[10, 5, 2, 6], k = 100 → 8. The product 10 × 5 × 2 = 100 is excluded.
Use the walkthrough below to inspect the input and each state change.
See Product below K, step by step
Expand, shrink, and inspect the window state.
4 elements · zero-based indicesk = 100
Current windowRecorded answerOutside window
- Left
- 0
- Right
- -1
- Length
- 0
Step 01 / 11
Start with an empty window
Both boundaries move forward. Watch what enters, what leaves, and when the answer changes.
left = 0; right = −1Answer so far
0
View exact input
Input: [10,5,2,6] · k = 100
Current window is empty.
Put it into code
With positive integers, dropping elements cannot increase a product. Restore product < k, then count all suffixes ending at right.
Indices are zero-based. C++ uses C++17 or later.
def product_below_k(nums, k):
# Positive integers only.
if k <= 1:
return 0
left = total = 0
product = 1
for right, value in enumerate(nums):
product *= value
while product >= k:
product //= nums[left]
left += 1
total += right - left + 1
return total#include <algorithm>
#include <array>
#include <deque>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
long long product_below_k(const vector<int>& nums, long long k) {
// nums[i] <= 10^6, k <= 10^9: intermediate product fits.
if (k <= 1) return 0;
int left = 0;
long long product = 1, total = 0;
for (int r = 0; r < (int)nums.size(); ++r) {
product *= nums[r];
while (product >= k) product /= nums[left++];
total += r - left + 1;
}
return total;
}