472. Subarray Product Less Than K
You get an array nums of positive integers and an integer k. Count how many contiguous subarrays have a product of elements that is strictly less than k, and return that count.
A subarray is a non-empty run of consecutive elements; two subarrays covering different index ranges count separately even if their contents look the same. Because every element is at least 1, extending a subarray can never shrink its product — that monotonicity is the door to a linear-time answer.
Watch the small values of k: if k is 0 or 1, no product of positive integers can be below it, so the answer is 0.
Example 1:
Input: nums = [2, 5, 3, 10], k = 30
Output: 6
Explanation: The qualifying subarrays are [2], [5], [3], [10], [2, 5] (product 10) and [5, 3] (product 15). [3, 10] and [2, 5, 3] both hit exactly 30, which is not strictly less than k, and every longer run is bigger still.
Example 2:
Input: nums = [1, 1, 1], k = 2
Output: 6
Explanation: Every one of the 3 + 2 + 1 = 6 subarrays has product 1, which is less than 2.
Constraints:
- 1 ≤ nums.length ≤ 3 * 10⁴
- 1 ≤ nums[i] ≤ 1000
- 0 ≤ k ≤ 10⁶
Hints:
Brute force: fix the left end, extend to the right multiplying as you go, and stop the moment the product reaches k — positives only grow. What's the worst-case cost?
Count subarrays by their RIGHT end. If the longest valid window ending at index r starts at l, then exactly r − l + 1 valid subarrays end at r.
Maintain that window with a running product: multiply in nums[r], and while the product is >= k divide out nums[l] and advance l. Guard k <= 1 first, or the shrink loop has nothing sensible to do.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [2, 5, 3, 10], k = 30
Expected output: 6