Subarray Product Less Than K

Solution

Two Pointers

Every step right goes 1 step to the right. left is the smallest value so that the product in the window prod = nums[left] * nums[left + 1] * ... * nums[right] is less than k. The number of subarrays w/ right boundary is right - left + 1 and added to res.

Complexity

time: $O(n)$
space: $O(1)$

def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
    if k <= 1:
        return 0
    n = len(nums)
    prod = 1
    lo = 0
    res = 0
    for hi in range(n):
        prod *= nums[hi]
        while prod >= k:
            prod /= nums[lo]
            lo += 1
        res += hi-lo+1
    return res