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