# 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:
• space:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
if k<=1: return 0
prod = 1
n = len(nums)
res = left = 0
for right, val in enumerate(nums):
prod *= val
while prod>=k:
prod /= nums[left]
left += 1
res += right - left + 1
return res

Last Updated: 5/13/2020, 7:39:18 AM