Subarray Product Less Than K

medium array sliding window

Problem

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

Inputnums = [10, 5, 2, 6], k = 100

Output8

[10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6] all have product < 100.

nums (positive, comma-separated)

def num_subarray_product_less_than_k(nums, k):
    if k <= 1: return 0
    prod, ans, l = 1, 0, 0
    for r, x in enumerate(nums):
        prod *= x
        while prod >= k:
            prod //= nums[l]; l += 1
        ans += r - l + 1
    return ans

function numSubarrayProductLessThanK(nums, k) {
  if (k <= 1) return 0;
  let prod = 1, ans = 0, l = 0;
  for (let r = 0; r < nums.length; r++) {
    prod *= nums[r];
    while (prod >= k) { prod /= nums[l]; l++; }
    ans += r - l + 1;
  }
  return ans;
}

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

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

Explanation

We count how many contiguous subarrays have a product below k. Because all numbers are positive, growing a window only multiplies the product up, and shrinking it divides the product down — that monotonic behavior makes a sliding window perfect here.

We keep a window between l and r with a running prod. We push r rightward, multiplying in nums[r]. If prod reaches k or more, we divide out nums[l] and move l right until the product is back under k.

The key counting trick: once the window [l..r] is valid, every subarray that ends at r and starts anywhere from l to r is also valid. There are exactly r - l + 1 of those, so we add that to ans.

If k <= 1, no positive product can be smaller, so we return 0 immediately.

Example: nums = [10, 5, 2, 6], k = 100. Summing r - l + 1 across all valid right ends gives 8, matching the eight qualifying subarrays.

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