Count Segments with a Small Product
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Count the contiguous nonempty subarrays of nums whose element product is strictly smaller than k.
```cpp
class Solution {
public:
int numSubarrayProductLessThanK(vector<int>& nums, int k);
};
```
### Examples
**Example 1:**
```text
nums = [2,3,4], k = 12
Output: 4
Explanation: Three singletons and [2,3] qualify; [3,4] equals the limit.
```
**Example 2:**
```text
nums = [1,1], k = 1
Output: 0
Explanation: No positive product is smaller than 1.
```
### Constraints
- The array has between 1 and 30000 values.
- Each value belongs to [1,1000].
- The threshold k belongs to [0,1000000].
### Contract considerations
Use positivity to justify monotonic window movement; k may be zero.
```hint Read the boundary condition
How many valid suffixes end at the current right endpoint?
```
### Boundary reminders
Use positivity to justify monotonic window movement; k may be zero.
Overview: Count Segments with a Small Product. Count the contiguous nonempty subarrays of nums whose element product is strictly smaller than k.