LeetCode Solutions
713. Subarray Product Less Than K
Time: $O(n)$ Space: $O(1)$
class Solution {
public:
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
if (k <= 1)
return 0;
int ans = 0;
int prod = 1;
for (int l = 0, r = 0; r < nums.size(); ++r) {
prod *= nums[r];
while (prod >= k)
prod /= nums[l++];
ans += r - l + 1;
}
return ans;
}
};
class Solution {
public int numSubarrayProductLessThanK(int[] nums, int k) {
if (k <= 1)
return 0;
int ans = 0;
int prod = 1;
for (int l = 0, r = 0; r < nums.length; ++r) {
prod *= nums[r];
while (prod >= k)
prod /= nums[l++];
ans += r - l + 1;
}
return ans;
}
}
class Solution:
def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
if k <= 1:
return 0
ans = 0
prod = 1
j = 0
for i, num in enumerate(nums):
prod *= num
while prod >= k:
prod /= nums[j]
j += 1
ans += i - j + 1
return ans