LeetMotion
Given an array of integers nums and an integer k, return the number of contiguous subarrays where the product of all the elements in the subarray is strictly less than k.
nums[i] ≥ 1, the product never decreases as you add elements. When product ≥ k, you can shrink from the left by dividing out nums[l]. This monotonicity is what makes the sliding window valid here.[l..r] has product < k, every subarray ending at r with left boundary ≥ l is also valid (smaller product). That gives r - l + 1 valid subarrays: [r..r], [r-1..r], ..., [l..r]. Add this count at each step.Imagine consecutive trading days where each day's value is a risk multiplier for that session. A compliance rule states that any consecutive investment period must have a cumulative risk multiplier (product) strictly below threshold k. You need to count all such valid consecutive periods. The sliding window expands to include more days and shrinks when the combined risk exceeds the threshold — identifying every compliant window in a single O(n) sweep.
The key insight: once you have a valid window [l..r] with product < k, there are exactly r - l + 1 subarrays ending at r that are all valid. You add this count at every step rather than enumerating each subarray individually.
k ≤ 1, return 0 immediately.l = 0, product = 1, count = 0.r: multiply product *= nums[r].product ≥ k: divide product //= nums[l], increment l.r - l + 1 to count. Return count.Each element is multiplied in once and divided out at most once. Total operations = O(n) with O(1) extra space. No sorting or prefix products needed.
Discussion
…