Count Subarrays With Product Less Than K
Implement countSubarraysWithProductLessThanK
Given an array of positive integers
nums and an integer k, count the number of contiguous subarrays whose product of all elements is strictly less than k.
Checking every subarray directly works but repeats the same multiplications across overlapping windows. The key trick is that with all-positive values, a sliding windowSliding WindowMaintaining a running result over a contiguous range that grows or shrinks one element at a time, instead of recomputing the result for every range from scratch. whose product stays under k can never help by shrinking further — so once a window [left, right] qualifies, every one of its right - left + 1 suffixes ending at right qualifies too, and they can all be counted in a single step.
Example 1:
Input: nums = [10,5,2,6], k = 100
Output: 8
Example 2:
Input: nums = [1,2,3], k = 0
Output: 0
Example 3:
Input: nums = [1,1,1], k = 2
Output: 6
+ 7 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ nums.length ≤ 3 × 10⁴ - ●
1 ≤ nums[i] ≤ 1000 - ●
0 ≤ k ≤ 10⁶
nums =
[10, 5, 2, 6]
k =
100