Subarray Product Less Than K

Intuition

Fix the right end of the window and ask how many valid subarrays end exactly there. Because all numbers are positive, once the window product drops below k it is the widest valid window ending at that right index, and every suffix of that window is also valid. The count of such subarrays ending at the right index is simply the window length. Sliding the left pointer only ever moves forward, so each element enters and leaves the window at most once.

Algorithm walkthrough

1. 1Handle the trivial case: if k is 1 or less, no product of positive integers can be strictly smaller, so return 0.
2. 2Walk a right pointer across the array, multiplying its value into a running product.
3. 3While the product is at least k, divide out the element at the left pointer and move the left pointer forward.
4. 4Add (right - left + 1) to the answer, which is the number of valid subarrays ending at the current right index.
5. 5Return the accumulated count after the sweep finishes.

Implementation

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        if k <= 1:
            return 0
        prod = 1
        left = 0
        count = 0
        for right, val in enumerate(nums):
            prod *= val
            while prod >= k:
                prod //= nums[left]
                left += 1
            count += right - left + 1
        return count