Problem Breakdown
We need to count all contiguous subarrays within a given array of positive integers where their product is strictly less than a target value k.
Inputs:
- An array
numscontaining only positive integers (1 or greater). - A threshold integer
k.
Outputs:
- The total number of valid subarrays.
Constraints & Edge Cases to Consider:
- Positive Integers Only: Since every element is , multiplying more elements never decreases the product. This monotonicity is key for optimization.
- Threshold : If
kis less than or equal to 1, no subarray can satisfy the condition because the minimum possible product of positive integers is 1 (e.g.,[1]). We must handle this immediately to avoid infinite loops or incorrect logic in sliding window. - Large : With length up to 50,000, an solution will time out. We need something closer to linear time.
Intuition
A brute-force approach would iterate through every possible start and end index for subarrays () and calculate the product each time (potentially leading to overflow or redundant calculations). Even optimizing the inner loop doesn’t change the worst-case complexity significantly enough for .
Key Insight: Because all numbers are positive integers , expanding a window from left to right always increases (or maintains) the product. Conversely, shrinking from the left decreases it. This monotonic behavior allows us to use a Sliding Window / Two Pointers technique.
For any valid subarray ending at index right, if we know the smallest starting index left such that the window [left...right] has a product , then all windows between left and right (inclusive) are also valid because removing elements from the left only reduces or keeps the product constant. Thus, for each step of right, we simply add (right - left + 1) to our count after adjusting left.
Approach
- Handle Base Case: If , return 0 immediately since all elements are .
- Initialize Variables: Set a sliding window pointer
leftat the start, and maintain a running product variable initialized to 1. Initialize count to 0. - Iterate with Right Pointer: Loop through each element in
nums, treating it as the end of our current subarray (right). - Expand Window: Multiply the current window’s product by
nums[right]. - Shrink Window if Needed: While the running product is , divide the product by
nums[left]and incrementleft. This ensures we maintain a valid state whereproduct < k. Note: If an individual element itself causes overflow or exceeds (e.g.,[10, ...], ), this loop will shrink until the window is empty (left > right). - Count Valid Subarrays: Once the product condition is met for
right, every subarray ending atrightstarting from any index betweenleftandrightis valid. Add(right - left + 1)to count. - Return Result.
Complexity Analysis
- Time Complexity: . The
rightpointer moves forward once, and theleftpointer also moves at most as many times (each element enters and leaves the window exactly once). Operations inside are constant time arithmetic. - Space Complexity: . We only use a few integer variables for pointers and product tracking regardless of input size.
Solution
def numSubarrayProductLessThanK(nums, k):
# If k <= 1, no subarray can have product < k since nums[i] >= 1
if k <= 1:
return 0
left = 0
prod = 1
count = 0
for right in range(len(nums)):
prod *= nums[right]
# Shrink window from the left until product is strictly less than k
while prod >= k and left <= right:
prod //= nums[left]
left += 1
# All subarrays ending at 'right' starting between 'left' and 'right' are valid.
count += (right - left + 1)
return count
# Example usage matching problem description
nums = [10, 5, 2, 6]
k = 100
print(numSubarrayProductLessThanK(nums, k)) # Output: 8
Edge Cases Handled
- : Explicitly returns 0 at the start to prevent logic errors where product never drops below .
- Single element : The
whileloop condition ensures that if a single number makes the window invalid, we shrink untilleft > right, resulting in adding 0 for that step (correct behavior). - Product Overflow: Python handles large integers automatically. However, since and elements are small, standard integer arithmetic is safe without modulo logic needed here.