# 27.03.2024 [713. Subarray Product Less Than K]
Subarrays count with product less than `k` #medium
27.03.2024
713. Subarray Product Less Than K medium
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/551
Problem TLDR
Subarrays count with product less than k
#medium
Intuition
Let’s try to use two pointers and move them only once:
// 10 5 2 6 1 1 1 cnt
// i 10 1
// j
// * j 50 +5 3
// * j (100) +2 4
// i 10 5
// * * j 60 +6 7
// * * * j 60 +1 9
// * * * * j 60 +1 11
// * * * * * j 60 +1 13
// i * * * * 12 +1 15
// i * * * 6 +1 17
// i * * 1 +1 19
// i * 1 +1 21
// i 1 +1 23
As we notice, this way gives the correct answer. Expand the first pointer while p < k
, then shrink the second pointer.
Approach
Next, some tricks:
move the right pointer once at a time
move the second until conditions are met
adding
(i - j)
helps to avoid moving the left pointerif we handle the corner cases of
k = 0
andk = 1
, we can use some optimizations:nums[j]
will always be less thank
afterwhile
loop; andi
will always be less thani
in awhile
loop.
Complexity
Time complexity:
O(n)Space complexity:
O(1)
Code
fun numSubarrayProductLessThanK(nums: IntArray, k: Int): Int {
var i = 0; var j = 0; var res = 0; var p = 1
if (k < 2) return 0
for (j in nums.indices) {
p *= nums[j]
while (p >= k) p /= nums[i++]
res += j - i + 1
}
return res
}
pub fn num_subarray_product_less_than_k(nums: Vec<i32>, k: i32) -> i32 {
if k < 2 { return 0 }
let (mut j, mut p, mut res) = (0, 1, 0);
for i in 0..nums.len() {
p *= nums[i];
while p >= k { p /= nums[j]; j += 1 }
res += i - j + 1
}
res as i32
}