Subarray Product Less Than K
Problem
Given an array of positive 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.
- 1 ≤ nums.length ≤ 3 * 10⁴
- 1 ≤ nums[i] ≤ 1000
- 0 ≤ k ≤ 10⁶
Example
nums = [10, 5, 2, 6], k = 1008The brute-force approach would check every subarray and calculate its product, which is O(n²) and inefficient. Instead, the algorithm uses a sliding window to maintain a product of elements within a window. Starting with left and right pointers at the beginning, it expands the right pointer, multiplying the current product by nums[right]. If the product becomes greater than or equal to k, it shrinks the window from the left by dividing out nums[left] and moving left forward until the product is less than k again. At each step, the number of valid subarrays ending at right is right - left + 1, which accumulates the count. This approach efficiently counts all valid subarrays in O(n) time.
Approach
Straightforward Solution
A brute-force approach enumerates all subarrays and calculates their products, resulting in O(n²) time complexity, which is too slow for large inputs.
Core Observation
Since all elements are positive, expanding the window always increases the product and shrinking it always decreases it. Therefore, once the product reaches or exceeds k, the only way to restore a valid window is to move the left pointer forward until the product drops below k again. This behavior is what allows a linear-time sliding-window solution.
Path to Optimal
Recognizing that the problem asks for contiguous subarrays with a product constraint suggests a sliding window approach. The key insight is to maintain a window with a product less than k by expanding the right pointer and shrinking the left pointer as needed. This allows counting all valid subarrays ending at each right index in O(1) time per step, leading to an O(n) solution.
Optimal Approach
Use two pointers, left and right, to define a sliding window. Initialize product to 1. Iterate right over the array, multiplying product by nums[right]. While product >= k, divide product by nums[left] and increment left to shrink the window. At each right, add right - left + 1 to the answer, representing all valid subarrays ending at right. Return the accumulated answer after processing all elements.
Time
O(n)
Each element is visited at most twice: once when the right pointer expands the window and once when the left pointer shrinks it. Multiplications and divisions are constant time operations.
Space
O(1)
Only a few integer variables are used to track the product, pointers, and the answer. No additional data structures scale with input size.
Pattern Spotlight
Sliding Window (Variable Size with Multiplicative Constraint)
When counting contiguous subarrays constrained by a product or sum, maintain a window that expands greedily and contracts only when the constraint is violated, enabling O(n) enumeration of all valid subarrays by counting the window size at each step.
Solution
| 1 | class Solution: |
| 2 | def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int: |
| 3 | if k <= 1: |
| 4 | return 0 |
| 5 | |
| 6 | ans = left = 0 |
| 7 | curr = 1 |
| 8 | |
| 9 | for right in range(len(nums)): |
| 10 | curr *= nums[right] |
| 11 | while curr >= k: |
| 12 | curr //= nums[left] |
| 13 | left += 1 |
| 14 | |
| 15 | ans += right - left + 1 |
| 16 | |
| 17 | return ans |
Step-by-Step Solution
Handle Edge Case Where k is Less Than or Equal to 1
| 3 | if k <= 1: |
| 4 | return 0 |
Objective
To immediately return 0 when k is less than or equal to 1, since no positive product subarray can be strictly less than k in this case.
Key Insight
Since all nums[i] are positive integers, the smallest product of any subarray is at least 1. If k ≤ 1, no subarray product can be strictly less than k, so the answer is zero without further computation.
Interview Quick-Check
Core Logic
Recognize that k ≤ 1 is a trivial no-solution case due to positive integer constraints.
State & Boundaries
Return immediately to avoid unnecessary processing and potential division by zero.
Initialize Sliding Window State and Accumulators
| 6 | ans = left = 0 |
| 7 | curr = 1 |
Objective
To set up the initial state variables for the sliding window: answer accumulator, left pointer, and current product.
Key Insight
Initializing ans and left to zero and curr to one prepares the algorithm to start expanding the window from the beginning. The product starts at 1 because it is the multiplicative identity, allowing incremental multiplication as the window grows.
Interview Quick-Check
Core Logic
Initialize product to 1 to correctly accumulate multiplicative values as the window expands.
State & Boundaries
Left pointer starts at 0 to represent the start of the window.
Expand Window and Adjust Left Pointer to Maintain Product Constraint
| 9 | for right in range(len(nums)): |
| 10 | curr *= nums[right] |
| 11 | while curr >= k: |
| 12 | curr //= nums[left] |
| 13 | left += 1 |
Objective
To iterate over the array with the right pointer, multiply the current product by nums[right], and shrink the window from the left while the product violates the constraint.
Key Insight
By multiplying curr by nums[right], the window expands to include the new element. If the product exceeds or equals k, the window is shrunk from the left by dividing out nums[left] and incrementing left until the product is less than k again. This dynamic resizing maintains the invariant that the product of the current window is always less than k.
Interview Quick-Check
Core Logic
Maintain a sliding window where the product of elements is always less than k by expanding right and contracting left as needed.
State & Boundaries
The while loop ensures the window shrinks until the product constraint is restored.
Common Pitfalls & Bugs
Forgetting to shrink the window when product >= k leads to incorrect counts and potential infinite loops.
Accumulate Count of Valid Subarrays Ending at Current Right Index
| 15 | ans += right - left + 1 |
Objective
To add the number of valid subarrays ending at the current right pointer to the answer accumulator.
Key Insight
At each step, the number of valid subarrays ending at right is the size of the current window, which is right - left + 1. Adding this count accumulates all valid subarrays efficiently without enumerating them explicitly.
Interview Quick-Check
Core Logic
Count all subarrays ending at right by adding the current window size, leveraging the maintained product constraint.
Complexity
This counting method avoids enumerating subarrays explicitly, keeping the algorithm O(n).
Return the Total Count of Valid Subarrays
| 17 | return ans |
Objective
To return the accumulated count of all contiguous subarrays with product less than k.
Key Insight
After processing all elements, the accumulated answer represents the total number of valid subarrays. Returning it completes the algorithm.
Interview Quick-Check
Core Logic
Return the final accumulated count after processing the entire array.
Line Analysis
This solution has 3 Critical lines interviewers watch for.
ans += right - left + 1Add the count of valid subarrays ending at right to the answer.
The number of valid subarrays ending at right is the current window size (right - left + 1), so adding this accumulates all valid subarrays efficiently.
if k <= 1:Check if k is less than or equal to 1.
Since all elements are positive, no product can be less than 1, so if k ≤ 1, no valid subarray exists and the function can return 0 immediately.
while curr >= k:While product is greater than or equal to k, shrink window from the left.
This loop enforces the product constraint by removing elements from the left until the product is less than k again, maintaining the sliding window invariant.
return 0Return 0 for the trivial no-solution case.
This early return prevents unnecessary computation and avoids division by zero or invalid window operations later.
curr *= nums[right]Multiply current product by nums[right] to include new element.
Updating the product to include the new element maintains the product of the current window, enabling constraint checks.
curr //= nums[left]Divide product by nums[left] to remove leftmost element.
Removing the leftmost element from the product correctly updates the window's product as the window shrinks.
curr = 1Initialize current product to 1.
Product starts at 1 because it is the multiplicative identity, allowing correct incremental multiplication as the window expands.
left += 1Increment left pointer to shrink the window.
Moving left forward effectively shrinks the window, ensuring the product constraint is restored.
ans = left = 0Initialize answer accumulator and left pointer.
Starting ans and left at zero sets the initial state for counting subarrays and defining the sliding window's left boundary.
return ansReturn the total count of valid subarrays.
After processing all elements, the accumulated answer represents the total number of valid subarrays, completing the solution.
for right in range(len(nums)):Iterate over nums with right pointer.
The right pointer expands the sliding window by moving through each element in the array sequentially.
Test Your Understanding
Why does adding right - left + 1 to the answer at each step correctly count all valid subarrays ending at right?
Because all subarrays ending at right with start indices from left to right are guaranteed to have a product less than k, so their count is exactly right - left + 1.
Related Problems
Sliding Window pattern
Don't just read it. Drill it.
Reconstruct Subarray Product Less Than K from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Subarray Product Less Than K drill