Subarray Product Less Than K

Counting subarrays one by one is quadratic. The lever that unlocks a linear pass is that every value is positive: extending a window can only grow its product, and shrinking it can only reduce the product. That monotonicity means the window product is a well-behaved two-pointer quantity — the left edge only ever needs to move forward, and for each right edge the number of valid subarrays ending there is completely determined by where the left edge landed.

Brute Force: Enumerate Every Subarray

Time O(n²)Space O(1)

The direct reading of the problem: consider every contiguous subarray and check its product. Fix the start i, then extend the end j one step at a time while carrying the running product forward, so each new subarray costs a single multiplication. Whenever the running product is less than k, count it.

class Solution:
    def numSubarrayProductLessThanK(self, nums: list[int], k: int) -> int:
        count = 0
        for i in range(len(nums)):
            product = 1
            for j in range(i, len(nums)):
                product *= nums[j]
                if product < k:
                    count += 1
        return count

Why it is quadratic: there are n * (n + 1) / 2 subarrays, and the outer loop fixes each possible start while the inner loop walks to the end, so the nested loops touch every one of them. The running product means each subarray is checked in O(1), but the total work is still O(n²), which is too slow for n up to 30,000. Only a few integers of state are stored, so the extra space is O(1).

Sliding Window

OptimalTime O(n)Space O(1)

Keep a window [left, right] whose product is strictly less than k, and grow right one position at a time. Multiplying by the new element can push the product to k or above; when that happens the window is illegal, and because all values are positive the only way to fix it is to drop elements from the left. Advance left (dividing the product back down each time) until the product is below k or the window becomes empty.

The payoff is the counting step. Once the window is legal, every subarray that ends at right and starts anywhere in [left, right] is valid — the product of a larger subarray only grows, so any start before left would already be too big, and every start at or after left is a subarray of a window already known to be legal. There are exactly right - left + 1 such starts, so the answer grows by that amount at each right edge.

class Solution:
    def numSubarrayProductLessThanK(self, nums: list[int], k: int) -> int:
        count = 0
        left = 0
        product = 1
        for right, x in enumerate(nums):
            product *= x
            # Restore a legal window: positive values mean we can only shrink.
            while left <= right and product >= k:
                product //= nums[left]
                left += 1
            # Every start in [left, right] yields a valid subarray ending here.
            count += right - left + 1
        return count

Watch the window slide on nums = [10, 5, 2, 6], k = 100. The point to follow is how the left edge jumps past 10 when the product hits 100, and how the window width is added to the count on every right edge:

startk = 100

Input

10l

Window

[0..-1]

Product

Width r-l+1

Answer

after shrinking, every subarray ending at r and starting at or after l is valid, so it contributes r - l + 1

1 / 11

currentseendiscardedresult

All nums are positive, so extending the window grows the product and shrinking shrinks it. That monotonicity is what makes one moving window enough.

Why it is linear: right advances once per element, and left only ever moves forward, so across the whole scan each of the n elements is added to the window at most once and removed at most once. The inner while loop is therefore amortized O(1) per element, giving O(n) time total. The state is three integers plus the loop index, so the extra space is O(1).

Subarray Product Less Than K

Brute Force: Enumerate Every Subarray

Sliding Window

More Sliding Window practice