Count price windows whose product stays under a cap

Question

Given a list of positive numbers, count how many contiguous subarrays have a product strictly less than k. Think of the values as growth factors and k as a compounding cap.

nums = [10, 5, 2, 6], k = 100
-> 8

The 8 valid windows include [10], [5], [2], [6], [10,5] (50), [5,2] (10), [2,6] (12), and [5,2,6] (60).

Return the count of subarrays with product < k, in O(n) time.

Accepted Answer

Slide a window keeping a running product. Extend the right edge by multiplying in the new value; whenever the product reaches k or more, shrink from the left by dividing out values until it drops below k. For each right position, every window ending there and starting anywhere in [left, right] is valid, that is right - left + 1 new subarrays. Tracing [10,5,2,6], k=100: counts added per right index are 1, 2, 2, 3, summing to 8. (At index 2 the product hits 100, so the left edge advances past the 10.) Time O(n) (each index enters and leaves the window once), space O(1). Edge cases: k <= 1 yield…

Count price windows whose product stays under a cap

Your answer

More Coding questions