Subarray Product Less Than K

medium LeetCode #713

sliding-window

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

Complexity

Show Complexity

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

Hints

Show 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

Show PY Solution

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