0713. Subarray Product Less Than K
https://leetcode.com/problems/subarray-product-less-than-k
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
ac
class Solution {
public int numSubarrayProductLessThanK(int[] nums, int k) {
// edge cases
if (nums == null || nums.length == 0 || k <= 1) return 0;
int windowProduct = 1;
int count = 0;
for (int r = 0, l = 0; r < nums.length; r++) {
windowProduct *= nums[r];
while (windowProduct >= k) {
windowProduct /= nums[l];
l++;
}
count += r - l + 1; // when a new element add to right, it forms window size new subarray
}
return count;
}
}
/*
key: how to process the window
sliding window idea: when window formed, do something.
*/
Previous0712. Minimum ASCII Delete Sum for Two StringsNext0714. Best Time to Buy and Sell Stock with Transaction Fee
Last updated
Was this helpful?