Subarray Product Less Than K

Given an array of integers nums and an integer k, return the number of contiguous subarrays where the product of all elements is strictly less than k.

• A subarray is a contiguous sequence; we count how many such subarrays satisfy product < k.
• In the classic version, nums contains only positive integers; if k <= 1, no positive product can be < k, so return 0.
• If the array can contain zeros or negatives, the problem changes (product can become zero or negative; counting valid subarrays requires different handling).

• For positive-only arrays, expanding the window increases the product and shrinking decreases it. So for each right, we can shrink left until the product of [left..right] is less than k; then every subarray ending at right with start in [left, right] has product < k — that is right - left + 1 subarrays.
• We maintain the product of the current window; when we add nums[right], we multiply; when we shrink, we divide by nums[left].
• If k <= 1, we never have a positive product < k, so the answer is 0.

High-level: For each right, find the smallest left such that the product of [left..right] is < k. Then all subarrays ending at right with start in [left, right] are valid; add right - left + 1 to the count.

Steps:

1. If k <= 1, return 0. Initialize left = 0, prod = 1, count = 0.
2. For each right: prod *= nums[right]. While prod >= k, divide prod by nums[left] and left++.
3. Add right - left + 1 to count (all subarrays ending at right with start in [left, right]).
4. Return count.

• Time: O(n).
• Space: O(1).

• What if elements can be zero or negative?