106. Subarray Product Less Than K

Given an array of integers nums and an integer k, return the number of contiguous subarrays where the product of all elements is strictly less than k.

Input: Positive integer array nums and integer k.

Output: Integer — count of subarrays with product < k.

Examples

Input: [10,5,2,6],100
Output: 8
Explanation: Subarrays with product<100: [10],[5],[2],[6],[10,5],[5,2],[2,6],[5,2,6]. Count=8.

Input: [1,2,3],0
Output: 0
Explanation: k=0 so no product<0.

Input: [1,1,1,1],2
Output: 10
Explanation: All subarrays of all 1s have product 1<2.

Constraints

• 1<=nums.length<=3*10^4
• 1<=nums[i]<=1000
• 0<=k<=10^6

Asked by