Maintained by Vikas Dulgunde, software engineer
You are handed an array of positive integers and a single positive integer k. A contiguous slice, or subarray, is a run of one or more neighbouring values taken in their original order with nothing skipped. The task is to count every such slice whose elements multiply together to something strictly less than k.
Because all the numbers are positive, the product of a slice can only grow as you add more elements to it and can only shrink as you drop elements from the front. That monotonic behaviour is the lever that makes an efficient solution possible.
Watch the edge where k is very small. When k is 0 or 1, no product of positive integers can ever fall below it, since the smallest possible product is 1, so the answer is simply 0.
Return a single integer: the total number of qualifying subarrays.
The qualifying slices are [10], [5], [2], [6], [10,5], [5,2], [2,6], and [5,2,6]. The slice [10,5,2] multiplies to exactly 100, which is not strictly less than 100, so it does not count.
Every slice has a product of at least 1, so nothing is strictly below 1. The same reasoning gives 0 for any k of 0 or 1.
Counting slices that stay under 10: [1], [2], [3], [4], [1,2], [2,3], and [1,2,3] (product 6). Slices like [3,4] (12) and [2,3,4] (24) are too large.
Visible test cases
Since every number is positive, a window's product never decreases when you push a new element onto the right and never increases when you pop one off the left. That gives you a clean monotonic property to exploit.
Slide a window with two pointers. Keep multiplying in the new right element, and whenever the running product reaches k or more, divide out elements from the left until it drops back under k.
Once the window ending at the right pointer is valid, every subarray that ends at that right index and starts anywhere inside the window is also valid. The count of those is the window length, right - left + 1, so add that each step. Handle k <= 1 up front by returning 0.
Enumerate every start and end, multiply the run as you extend it, and increment a counter whenever the running product stays under k.
Maintain a window whose product is always below k. Because the inputs are positive, growing the window on the right and shrinking it on the left moves the product in predictable directions, so each valid right end contributes a window's worth of subarrays at once.