Subarray Product Less Than K

Sliding Window

Problem

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:

Input: nums = [10, 5, 2, 6], k = 100
Output: 8
Explanation: 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.

Input: [2, 5, 3, 10], target=30 
Output: [2], [5], [2, 5], [3], [5, 3], [10]
Explanation: There are six contiguous 
subarrays whose product is less than the 
target.

Solution

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        product = 1
        left=0
        count = 0
        
        if k == 0:
            return 0
        
        for i in range(len(nums)):
            product*=nums[i]
            while product >= k and left<= i: 
                product/=nums[left]
                left+=1
            count+=i-left+1
        return count  
    
    #if its less than target then all the numbers in 
    #between products with one another will be less 
    #than target as well. This is why we do i-left+1
    
    #need l <= i in the case of target= 0 or 
    #1 where if you divide by the start of the
    #array it will be equal to 1 which is 
    #greater than/equal to 0/1, so it will 
    #continuosuly increase left index
    
    #Time: O(n)
    #Space: O(1)