Subarray Product Less Than K

Description

Given an array of positive integers nums and an integer k, return the number of contiguous subarrays where the product of all elements is strictly less than k.

Example 1:
Input: nums = [10, 5, 2, 6], k = 100
Output: 8
Explanation: The 8 subarrays with product < 100 are:
[10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]
Note: [10,5,2] has product 100 which is NOT less than 100.

Example 2:
Input: nums = [1, 2, 3], k = 0
Output: 0
Explanation: No subarray has product less than 0 (all products are positive).

Example 3:
Input: nums = [1, 1, 1], k = 2
Output: 6
Explanation: All subarrays have product = 1 which is < 2.
[1], [1], [1], [1,1], [1,1], [1,1,1] = 6 subarrays.

Constraints

1 <= nums.length <= 3 * 10^4
1 <= nums[i] <= 1000
0 <= k <= 10^6

Signature

def solution(nums: list[int], k: int) -> int: ...

Complexity

Time: O(n)
Space: O(1)

Hints

Pattern: Use a sliding window with product tracking
Approach: Multiply by nums[right]. While product >= k, divide by nums[left++]. Add (right - left + 1) to count.
Complexity: Each valid window of size n contributes n new subarrays (ending at right)

Solutions

Python

def solution(nums, target):
    if target <= 1:
        return 0

    result = 0
    acc = 1
    left = 0
    for right in range(len(nums)):
        acc *= nums[right]

        while acc >= target:
            acc /= nums[left]
            left += 1

        result += right - left + 1

    return result