Your are given an array of positive integers nums. Count and print the number of (contiguous) subarrays where the product of all the elements in the subarray is less than k.

For example, given the array nums = [10, 5, 2, 6], k = 100

Answer is 8

The 8 subarrays that have product less than 100 are: [10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6]. Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k

The problem is very similar to subarray with sum of kbut with a small difference, in this case we have to find product.

The problem can be solved by maintaining 2 pointers, very similar to minimum window substring. start,endpointers will be used to manage the size of window with sum k. The algorithm is as follows:

Increment the start index and product elements along the path, continue mulitply up elements as long it is not greater than k

Once the product is greater than or equal to k. Start incrementing the end index and decrease the value arr[end] from product.

If the product is less than k, that is the window size. Check if the size(start-end) is minimum, continue above step until end of array is reached

public class Solution {
public int productLessThanK(int[] nums, int k) {
if (k <= 1) return 0;
int prod = 1, ans = 0, left = 0;
for (int right = 0; right < nums.length; right++) {
prod *= nums[right];
while (prod >= k) prod /= nums[left++];
ans += right - left + 1;
}
return ans;
}
}