Array
Binary Search
Prefix Sum
Sliding Window
Description
Given an array of 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
.
Example 1:
Input: nums = [10,5,2,6], k = 100
Output: 8
Explanation: The 8 subarrays that have product less than 100 are:
[10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6]
Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k.
Example 2:
Input: nums = [1,2,3], k = 0
Output: 0
Constraints:
1 <= nums.length <= 3 * 104
1 <= nums[i] <= 1000
0 <= k <= 106
Solutions
Solution 1
Python3 Java C++ Go TypeScript Rust JavaScript Kotlin
class Solution :
def numSubarrayProductLessThanK ( self , nums : List [ int ], k : int ) -> int :
ans , s , j = 0 , 1 , 0
for i , v in enumerate ( nums ):
s *= v
while j <= i and s >= k :
s //= nums [ j ]
j += 1
ans += i - j + 1
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13 class Solution {
public int numSubarrayProductLessThanK ( int [] nums , int k ) {
int ans = 0 ;
for ( int i = 0 , j = 0 , s = 1 ; i < nums . length ; ++ i ) {
s *= nums [ i ] ;
while ( j <= i && s >= k ) {
s /= nums [ j ++] ;
}
ans += i - j + 1 ;
}
return ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12 class Solution {
public :
int numSubarrayProductLessThanK ( vector < int >& nums , int k ) {
int ans = 0 ;
for ( int i = 0 , j = 0 , s = 1 ; i < nums . size (); ++ i ) {
s *= nums [ i ];
while ( j <= i && s >= k ) s /= nums [ j ++ ];
ans += i - j + 1 ;
}
return ans ;
}
};
func numSubarrayProductLessThanK ( nums [] int , k int ) int {
ans := 0
for i , j , s := 0 , 0 , 1 ; i < len ( nums ); i ++ {
s *= nums [ i ]
for ; j <= i && s >= k ; j ++ {
s /= nums [ j ]
}
ans += i - j + 1
}
return ans
}
function numSubarrayProductLessThanK ( nums : number [], k : number ) : number {
let ans = 0 ;
for ( let i = 0 , j = 0 , s = 1 ; i < nums . length ; ++ i ) {
s *= nums [ i ];
while ( j <= i && s >= k ) {
s /= nums [ j ++ ];
}
ans += i - j + 1 ;
}
return ans ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 impl Solution {
pub fn num_subarray_product_less_than_k ( nums : Vec < i32 > , k : i32 ) -> i32 {
if k <= 1 {
return 0 ;
}
let mut res = 0 ;
let mut product = 1 ;
let mut i = 0 ;
nums . iter (). enumerate (). for_each ( | ( j , v ) | {
product *= v ;
while product >= k {
product /= nums [ i ];
i += 1 ;
}
res += j - i + 1 ;
});
res as i32
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 /**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var numSubarrayProductLessThanK = function ( nums , k ) {
const n = nums . length ;
let ans = 0 ;
let s = 1 ;
for ( let i = 0 , j = 0 ; i < n ; ++ i ) {
s *= nums [ i ];
while ( j <= i && s >= k ) {
s = Math . floor ( s / nums [ j ++ ]);
}
ans += i - j + 1 ;
}
return ans ;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 class Solution {
fun numSubarrayProductLessThanK ( nums : IntArray , k : Int ): Int {
var left = 0
var count = 0
var product = 1
nums . forEachIndexed { right , num ->
product *= num
while ( product >= k && left <= right ) {
product /= nums [ left ++]
}
count += right - left + 1
}
return count
}
}