Problem Description

Given an array of positive integers nums and an integer k, your task is to find the number of contiguous subarrays where the product of all the elements in the subarray is less than k.

• Each subarray must be contiguous (elements must be next to each other in the original array).
• Elements cannot be reused in a subarray.
• If there are no such subarrays, return 0.
• All numbers in nums are positive integers.
• Constraints typically include: 1 <= nums.length <= 3 * 10^4, 1 <= nums[i] <= 1000, 0 <= k <= 10^6.

Thought Process

At first glance, you might think to check every possible contiguous subarray, calculate its product, and count it if the product is less than k. This brute-force approach is simple to understand but not efficient, especially for large arrays. For each starting index, we would try every ending index, multiply the elements, and check if the product stays below k.

However, this approach is slow because it checks every subarray individually, leading to a time complexity of O(n²) or worse. To optimize, we need a way to avoid recalculating products from scratch for overlapping subarrays. Since all elements are positive, we can use a sliding window technique, expanding and shrinking a window over the array to efficiently keep track of the product.

The key insight is: if the product of elements from left to right is less than k, then all subarrays ending at right and starting from any index between left and right are also valid.

Solution Approach

To solve the problem efficiently, we'll use the sliding window (two-pointer) technique:

1. Initialize two pointers, left and right, both at 0, and set prod = 1 (the running product).
2. Iterate right from 0 to the end of the array:
• Multiply prod by nums[right].
• While prod >= k and left <= right, divide prod by nums[left] and increment left. This shrinks the window until the product is less than k.
• At each step, the number of valid subarrays ending at right is right - left + 1.
3. Sum up these counts for each right position to get the total number of valid subarrays.
4. Return the total count.

This method works efficiently because it avoids redundant calculations and leverages the properties of positive numbers (products only increase as you add elements, so shrinking the window is safe).

Example Walkthrough

Let's use nums = [10, 5, 2, 6] and k = 100 as an example.

• Start: left = 0, prod = 1, count = 0
• right = 0: prod = 1 * 10 = 10 < 100; add (0 - 0 + 1) = 1 subarray ([10])
• right = 1: prod = 10 * 5 = 50 < 100; add (1 - 0 + 1) = 2 subarrays ([10,5], [5])
• right = 2: prod = 50 * 2 = 100 == 100; too large, shrink window:
  • prod /= nums[0] → 100 / 10 = 10; left = 1
  Now prod = 10 < 100; add (2 - 1 + 1) = 2 subarrays ([5,2], [2])
• right = 3: prod = 10 * 6 = 60 < 100; add (3 - 1 + 1) = 3 subarrays ([5,2,6], [2,6], [6])

Total = 1 + 2 + 2 + 3 = 8 valid subarrays.

Time and Space Complexity

• Brute-force approach:
  • Time: O(n²) — For each start index, try all end indices and compute the product.
  • Space: O(1) — Only a few variables needed.
• Optimized sliding window approach:
  • Time: O(n) — Each element is visited at most twice (once by right, once by left).
  • Space: O(1) — Only a few pointers and a running product.

The optimized approach is much faster for large arrays.

Code Implementation

class Solution:
    def numSubarrayProductLessThanK(self, nums, k):
        if k <= 1:
            return 0
        prod = 1
        result = 0
        left = 0
        for right, val in enumerate(nums):
            prod *= val
            while prod >= k:
                prod //= nums[left]
                left += 1
            result += right - left + 1
        return result
      

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

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

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

Summary

This problem demonstrates the power of the sliding window technique for efficiently counting subarrays under a product constraint. By exploiting the property that all numbers are positive, we avoid redundant calculations and achieve linear time. The key insight is that, for each window, all subarrays ending at the current index and starting at any valid left boundary are automatically valid, and we can count them in constant time. This makes the solution both elegant and practical for large inputs.