Given a slice of positive integers and a target, return the number of contiguous
subarrays whose product is strictly less than target.
countSubarrayProduct(nums, target)
Input format: nums | target.
[10, 5, 2, 6], target=100 // → 8
[1, 2, 3], target=0 // → 0
[1, 1, 1], target=2 // → 6
You need to count all contiguous subarrays with product strictly less than target — not just find one or the longest. Brute force checks every (start, end) pair from scratch — O(n²) at minimum. But every number here is positive, which gives the same monotonic reasoning as the sum problems, applied to products: extending with a positive number can only increase (or hold) the product; removing from the left can only decrease it.
For a fixed right endpoint, shrinking from the left only decreases the product. So there's a well-defined leftmost point beyond which the product is finally below target — and every starting point from there to right also gives a product below target, since starting further right only removes positive factors.
As the window expands with nums[right], the product may reach or exceed target. Shrink from the left, dividing out nums[left] and advancing, until the product drops back below target.
Once [left, right] is valid, every subarray ending at right and starting anywhere from left to right is also valid — removing factors from the front only shrinks the product further. So add right - left + 1 to the count in one step, instead of verifying each starting point.
nums[right].right - left + 1 to the total.right. Handle target ≤ 1 directly — no positive product can be that small.Both pointers only move forward — O(n) overall — and the batch-counting trick avoids enumerating O(n²) individual subarrays, counting a whole batch in O(1) per step.
def count_subarray_product(nums, target):
if target <= 1:
return 0
left = 0
product = 1
count = 0
for right in range(len(nums)):
product *= nums[right]
while product >= target:
product = int(product / nums[left])
left += 1
count += right - left + 1
return count
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.