Subarray Product Less Than K — Problem & Solution
Subarray Product Less Than K solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Subarray Product Less Than K is a medium coding problem on arrays, binary search and prefix sum, asked in Amazon, Google and Meta interviews.
- Difficulty: Medium
- Topics: Arrays, Binary Search, Prefix Sum, Sliding Window
- Asked at: Amazon, Google, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an array of positive integers nums and an integer k, return the number of contiguous subarrays whose product is strictly less than k.
Example 1
Input: nums = [10,5,2,6], k = 100
Output: 8
Explanation: The eight are [10], [5], [2], [6], [10,5], [5,2], [2,6] and [5,2,6].
Example 2
Input: nums = [1,2,3], k = 0
Output: 0
Explanation: No product is below 0.
Example 3
Input: nums = [1,1,1], k = 2
Output: 6
Constraints
1 <= nums.length <= 301 <= nums[i] <= 200 <= k <= 1000000
Hints for Subarray Product Less Than K
Hint 1
All values are positive, so growing the window can only increase the product — the window is monotone.
Hint 2
Expand right, then shrink from the left while the product is at least
k.Hint 3
A window
[left, right]contributesright - left + 1subarrays: every one that ends atright.
How to solve Subarray Product Less Than K
All values are positive, so a window's product only grows as it widens. Expand the right end, shrink from the left while the product is at least k, and count right - left + 1 subarrays ending at right.
Approach
- Return 0 if
k <= 1— no product of positive integers is below 1. - For each
right, multiplyproductbynums[right]. - While
product >= k, divide outnums[left]and advanceleft. - Add
right - left + 1to the count.
Why it works
Once the window [left, right] has product below k, every suffix of it — the subarrays ending at right — also does, and there are right - left + 1 of them. Monotonicity guarantees the left pointer never needs to move backwards.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Without the
k <= 1guard, the shrink loop can run pastrightwhen a single element already fails. - The comparison is strict —
product < k.
Reference solution
Python
def numSubarrayProductLessThanK(nums, k: int) -> int:
if k <= 1:
return 0
product, left, count = 1, 0, 0
for right, x in enumerate(nums):
product *= x
while product >= k:
product //= nums[left]
left += 1
count += right - left + 1
return countJava
public static int numSubarrayProductLessThanK(int[] nums, int k) {
if (k <= 1) return 0;
long product = 1;
int left = 0, count = 0;
for (int right = 0; right < nums.length; right++) {
product *= nums[right];
while (product >= k) {
product /= nums[left];
left++;
}
count += right - left + 1;
}
return count;
}C++
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
if (k <= 1) return 0;
long long product = 1;
int left = 0, count = 0;
for (int right = 0; right < (int) nums.size(); right++) {
product *= nums[right];
while (product >= k) {
product /= nums[left];
left++;
}
count += right - left + 1;
}
return count;
}JavaScript
var numSubarrayProductLessThanK = function(nums, k) {
if (k <= 1) return 0;
let product = 1, left = 0, count = 0;
for (let right = 0; right < nums.length; right++) {
product *= nums[right];
while (product >= k) {
product /= nums[left];
left++;
}
count += right - left + 1;
}
return count;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Binary Search