Community Problem
Subarray Product Less Than K
Difficulty: Medium
Count contiguous subarrays whose product is strictly less than k, in linear time using a sliding window.
Subarray Product Less Than K
Count contiguous subarrays whose product is strictly less than k, in linear time using a sliding window.
By @yukisantos
March 4, 2026
·
Updated May 20, 2026
817 views
13
4.3 (14)
Whoever first wrote this in a real interview deserves a coffee, because it is the cleanest example I know of the "count subarrays ending at right" sliding-window pattern. The official catalog has Subarray Sum Equals K (prefix-sum + hash) and Minimum Size Subarray Sum (window grow-shrink), but it skipped the multiplicative variant where the count of valid windows is exactly right - left + 1 at each step. Once that identity clicks, the algorithm is six lines.
Subarray Product Less Than K
Given an array of positive integers nums and an integer k, return the number of contiguous subarrays whose product of all elements is strictly less than k.
Examples
Example 1:
- Input:
nums = [10, 5, 2, 6],k = 100 - 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[10, 5, 2]has product 100 which is NOT strictly less than 100.
Example 2:
- Input:
nums = [1, 2, 3],k = 0 - Output:
0 - Explanation: All products are at least 1 (the array is positive), so none are less than
0.
Example 3:
- Input:
nums = [1, 1, 1],k = 2 - Output:
6 - Explanation: Every contiguous subarray has product
1which is less than2. Withn = 3there are3 + 2 + 1 = 6contiguous subarrays.
Example 4:
- Input:
nums = [10, 9, 10, 4, 3, 8, 3, 3, 6, 2, 10, 10, 9, 3],k = 19 - Output:
18 - Explanation: A larger mixed input; the canonical answer is 18.
Constraints
1 <= nums.length <= 3 * 10^41 <= nums[i] <= 10000 <= k <= 10^6
Follow-up
If k <= 1, the answer is always 0 because every product of positive integers is at least 1. Make sure your sliding window handles that boundary correctly (the inner shrink loop should not run forever).
Solution
Hints
Solution Walkthrough
Approach: Sliding Window with Counting Identity (O(n) time, O(1) space)
The key observation is that all values are positive, so the product of any window is monotone in the window's length: extending the window multiplies the product by something >= 1, never decreasing it. This means a standard variable-size sliding window works.
The second observation is the counting identity. When the window [left..right] has product strictly less than k, every subarray that ends at right and starts anywhere in [left..right] also has product less than k (because shrinking from the left can only divide out a positive factor >= 1). The number of such subarrays is right - left + 1. Sum that across right.
Algorithm
- If
k <= 1, return0(no positive product is< 1). - Initialize
left = 0,product = 1,count = 0. - For
rightfrom0ton - 1:- Multiply
productbynums[right]. - While
product >= k, divide outnums[left]and advanceleft. - Add
right - left + 1tocount.
- Return
count.
Why It Works
Loop invariant before adding to count at iteration right: the window [left..right] has product < k, OR left > right (empty window). When the window is non-empty and valid, the count of valid subarrays ending at right is right - left + 1: one for each possible left endpoint in [left..right]. When the inner loop has shrunk past right (so left == right + 1), the empty window contributes 0, which is the right answer because nums[right] itself is >= k.
The k <= 1 guard exists because the inner shrink loop divides by nums[left] only when nums[left] is part of the window. When right is freshly added and nums[right] >= k, the loop divides through every prior element until the window is empty. If k <= 1, no positive product is below k, so the loop would otherwise advance left past right + 1, which is fine in practice but the early return is cleaner and avoids the corner case.
Complexity
Metric Value
Time O(n), each index is visited at most once by left and once by right
Space O(1), only scalar accumulatorsPitfalls
- Strict vs non-strict inequality. The problem asks for product strictly less than
k. The shrink loop condition isproduct >= k, notproduct > k. Off-by-one here is the most common bug. - Integer division in JS. JavaScript's
/operator is floating-point, so dividing the product bynums[left]can introduce rounding error for large products. UsingMath.floor(product / nums[left])is safe under the constraints becausenums[left]always divides the product exactly (we multiplied it in earlier). - Negative or zero values in
nums. The algorithm only works for strictly-positivenums. If the constraints allowed0or negatives, the monotonicity argument breaks and you would need a different technique (e.g. prefix-product log + sorted structure). k <= 1corner case. Withk = 0ork = 1, no subarray of positive integers qualifies. Return0immediately.
Solution Code