Subarray Product Less Than K
Explanation & Solution
Description
Given an array of positive integers nums and an integer k, return the number of contiguous subarrays where the product of all the elements is strictly less than k.
Examples
Output: 8
Explanation: The 8 subarrays with product less than 100 are: [10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6]. Note that [10, 5, 2] is not included because the product (100) is not strictly less than k.
Output: 0
Explanation: No subarray has a product less than 0 since all elements are positive.
Output: 6
Explanation: All 6 subarrays have a product of 1, which is less than 2: [1], [1], [1], [1,1], [1,1], [1,1,1].
Constraints
1 <= nums.length <= 3 * 10^41 <= nums[i] <= 10000 <= k <= 10^6
Approach
Sliding Window pattern
1. Handle the Edge Case
If k <= 1, return 0 immediately. Since all elements are positive integers (>= 1), no product can be less than 1 or less than 0.
2. Initialize the Sliding Window
Set up a left pointer at index 0, a running product starting at 1, and a count of valid subarrays starting at 0.
3. Expand the Window
Iterate with a right pointer across the array. At each step, multiply the current element into the running product.
4. Shrink the Window When Needed
While product >= k, divide out the element at the left pointer and increment left. This contracts the window until the product is strictly less than k again.
5. Count Valid Subarrays
After adjusting the window, every subarray ending at right and starting at any index from left to right is valid. That gives us right - left + 1 new subarrays to add to our count.
Key Insight
The sliding window works because all elements are positive, meaning the product only grows as we expand the window and only shrinks as we contract it. For each position of right, the number of valid subarrays ending there is exactly the current window size (right - left + 1). This avoids checking all O(n^2) subarrays and gives us an O(n) solution.