Sliding Window

Subarray product less than K

leetcode

In order to find all subarrays with products less than k, use sliding window approach, expand the right side one step at a time, then shrink the window from the left side until the product inside the window is valid, i.e., strictly under k.

Now all subarrays inside [left, right] that ends at index right are all valid arrays. The number of these arrays is exactly right-left+1. And there won’t be any duplicate countings.

For example, when right = 0, left stays at 0, the only valid subarray is [10].

When right = 1, the current product is still below k, left stays at 0, valid subarrays(that ends at index right) are [[10, 5], [5]].

class Solution:
    def numberContiguousArrays(self, nums, k):
        left = 0
        cur_product = 1
        count = 0
 
        for right in range(len(nums)):
            cur_product *= nums[right]
 
            while left <= right and cur_product >= k:
                cur_product /= nums[left]
                left += 1
 
            count += (right - left + 1)
 
        return count