167. Product Under K
A growth model stores the monthly multipliers of an investment as an array of positive integers nums. A contiguous run of months is called safe if multiplying all of its multipliers together gives a value that is strictly smaller than the limit k.
Return the number of non-empty contiguous subarrays of nums whose product is strictly less than k. Two subarrays with the same values but different positions are counted separately. If k is 0 or 1, no product of positive integers can be below it, so the answer is 0. The answer fits in a 32-bit integer.
Example 1
- Input:
- nums = [2,3,1,4], k = 10
- Output:
- 8
- Explanation:
Eight subarrays have a product below 10: the four single elements, [2,3] (6), [3,1] (3), [1,4] (4) and [2,3,1] (6). The subarray [3,1,4] (12) and the whole array (24) are too large.
Example 2
- Input:
- nums = [5,5,5], k = 5
- Output:
- 0
- Explanation:
Every single element has product 5, which is not strictly below 5, so nothing qualifies and the answer is 0.
Example 3
- Input:
- nums = [1,1,1], k = 2
- Output:
- 6
- Explanation:
Every subarray has product 1, which is below 2, and there are 3 + 2 + 1 = 6 subarrays.
Constraints
1 ≤ nums.length ≤ 50000
1 ≤ nums[i] ≤ 1000
0 ≤ k ≤ 106
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)