Subarray Product Less Than K

Problem

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

Input:  nums = [10,5,2,6], k = 100
Output: 8

Python Solution

def num_subarray_product_less_than_k(nums, k):
    if k <= 1:
        return 0
    left = 0
    product = 1
    count = 0
    for right, num in enumerate(nums):
        product *= num
        while product >= k:
            product //= nums[left]
            left += 1
        count += right - left + 1
    return count

C++ Solution

int numSubarrayProductLessThanK(vector<int>& nums, int k) {
    if (k <= 1) return 0;
    int left = 0, count = 0;
    long product = 1;
    for (int right = 0; right < nums.size(); right++) {
        product *= nums[right];
        while (product >= k) {
            product /= nums[left];
            left++;
        }
        count += right - left + 1;
    }
    return count;
}

Java Solution

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k <= 1) return 0;
        int left = 0, count = 0;
        long product = 1;
        for (int right = 0; right < nums.length; right++) {
            product *= nums[right];
            while (product >= k) {
                product /= nums[left];
                left++;
            }
            count += right - left + 1;
        }
        return count;
    }
}

Complexity

Time: O(n) — the left pointer only moves forward. Space: O(1) — a running product and two pointers only. Each valid window of length L contributes L new subarrays, all ending at the current right pointer, which is why right - left + 1 is added directly to the count.