Subarray Product Less Than K

How it works

Since all numbers are positive, the product of a subarray increases as we add elements and decreases as we remove them. This monotonic property makes sliding window ideal. We maintain a window [l, r] where the product is less than k. When adding nums[r] causes the product to exceed or equal k, we shrink from the left until the product drops below k again. Each valid window ending at r contributes r - l + 1 new subarrays.

Steps

1. Initialize l = 0, product = 1, and res = 0.
2. For each r from 0 to n - 1:
   • Multiply product by nums[r].
   • While product >= k and l <= r, divide product by nums[l] and increment l.
   • Add r - l + 1 to res (this counts all subarrays ending at r with product < k).
3. Return res.

Complexity

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

Things to watch for

Forgetting the Edge Case When k <= 1

When k is 0 or 1, no positive product can be less than k. Failing to handle this edge case leads to incorrect results or infinite loops. Always check if k <= 1: return 0 at the start.

Using Strict Less-Than Comparison Incorrectly

The problem asks for products strictly less than k, not less than or equal. Using product <= k instead of product < k will overcount subarrays where the product equals exactly k.

Integer Overflow in Product Calculation

When multiplying elements together, the product can quickly exceed integer bounds. In languages like Java or C++, use long instead of int for the product variable to avoid overflow issues, especially with large arrays.

from typing import List
from itertools import product

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        res = 0
        l = 0
        product = 1
        for r in range(len(nums)):
            product *= nums[r]
            while l <= r and product >= k:
                product //= nums[l]
                l += 1
            res += (r - l + 1)
        return res

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