LC 0713 [M] Subarray Product Less Than K - ALawliet/algorithms GitHub Wiki

two-pointer + sliding window

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        count = 0
        product = 1
        l = 0
        for r in range(len(nums)):
            product *= nums[r]            
            while l <= r and not product < k:                   
                product /= nums[l]
                l += 1                        
            count += r - l + 1                
        return count
Input: nums = [10, 5, 2, 6], k = 100

======== (End for loop, r = 0 snapshot) =============
[10, 5, 2, 6]
  r
  l
prod = 10
cnt += 1


======== (End for loop, r = 1 snapshot) =============
[10, 5, 2, 6]
     r
  l
prod = 50
cnt += 2


======== (r = 2, prod >= k snapshot) ================
[10, 5, 2, 6]
        r
  l  
prod = 100, >= k, 
keep moving l till < k


======== (End for loop, r = 2 snapshot) =============
[10, 5, 2, 6]
        r
     l  
prod = 10
cnt += 2


======== (End for loop, r = 3 snapshot) =============
[10, 5, 2, 6]
           r
     l  
prod = 60	 
cnt += 3