Subarray Product Less Than K [Medium] — Sliding Window

Problem Statement

Count contiguous subarrays where the product of all elements is strictly less than k.

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

Intuition

Sliding window with running product. When product >= k, divide out the leftmost element and advance left. Number of valid subarrays ending at right = right - left + 1.

Solutions

C++

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

Java

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

Python

def numSubarrayProductLessThanK(nums: list[int], k: int) -> int:
    if k <= 1: return 0
    prod = left = ans = 0
    prod = 1
    for right, val in enumerate(nums):
        prod *= val
        while prod >= k:
            prod //= nums[left]; left += 1
        ans += right - left + 1
    return ans

Complexity

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