Low-Product Stretches
MediumSliding Window
Problem
A risk model multiplies consecutive growth factors nums (all positive integers). A stretch of consecutive factors is considered safe if its product is strictly less than `limit`.
Return the number of non-empty contiguous subarrays of nums whose product is strictly less than limit.
Example 1
- Input:
- nums = [4, 2, 6, 1], limit = 20
- Output:
- 8
Safe: [4], [2], [6], [1], [4, 2] = 8, [2, 6] = 12, [6, 1] = 6, [2, 6, 1] = 12. [4, 2, 6] = 48 and the whole array are not.
Example 2
- Input:
- nums = [1, 2, 3], limit = 1
- Output:
- 0
Every product is at least 1.
Constraints
- 1 ≤ nums.length ≤ 3·10^4
- 1 ≤ nums[i] ≤ 1000
- 0 ≤ limit ≤ 10^6
Hint
Show the first hint
With positive numbers, extending a subarray never decreases its product.
Walkthrough
How to approach it
01Clarify before coding
- Strictly less than limit? Yes, a product equal to limit is not safe.
- Can limit be 0 or 1? Yes; then nothing is safe because every product is ≥ 1.
- Do equal subarrays at different positions count separately? Yes.
02Brute force
For every start, multiply to the right until the product reaches limit, counting each safe extension.
Cost: O(n²) in the worst case (all ones), about 4.5·10^8 steps for n = 3·10^4.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.