LeetCode — 713. Subarray Product Less Than K
Q. 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.
Input: nums = [10,5,2,6], k = 100;
Output: 8
Explanation: There are total 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 the product of 100 is not strictly less than k.
First Lets talk about how to count the number of subarrays.
E.g nums = [10,5,2,6]
Basically a subarray is set of contiguous of elements in an array of size vary from 1 to n.
Subarray of size 1: [10], [5], [2],[6] — Total 4
Subarray of size 2: [10,5],[5,2],[2,6] — Total 3
Subarray of size 3: [10,5,2],[5,2,6] — Total 2
Subarray of size 4: [10,5,2,6] — Total 1
If you observe carefully the number of total subarrays of an array of size n is n + (n-1) + (n-2) + ........+ 2 + 1 + 0
First way to find the number of subarrays of an array that is [n*(n+1)]/2
Basically this is Arithmetic Progression.
For Example the nums size is 4 hence, total subarrays = (4*(4+1))/2 = 10
2nd ways to find the number of subarrays of an array
nums = [10,5,2,6]
size 1 = [10] = 1(0–0+1)
size 2 = [10,5] = 1 + 2(1–0+1)
size 3 = [10,5,2] = 1 + 2 + 3(2–0+1)
size 4 = [10,5,2,6] = 1 + 2 + 3 + 4(3–0+1);
Basically we keeps on adding the size on previous sum.
In above question we require product of subarrays less than 100.
let res = 0;
[10] — possible subarray
res + 1 = 0 + 1=1
[10,2] — possible subarray
Note: at this how many subarrays satisfy the condition is it 2? No. There are total three , how [10], [2],[10,2].
suppose we have array [10,2,3]
Then how many subarrays satisfy the condition
[10](1), [2],[10,2](1+2),[2,3],[3],[10,2,3](1+2+3) and so on..
I hope you understand the process, how we are getting count of subarrays step by step.
I our code we will also use above method instead of directly using formula((n*(n+1))/2).
In our code, we are going to use sliding window algorithm.
Maintain left pointer and right pointer. Once the product exceed the thresold(k). We will keep increasing left pointer until the product becomes lesser than k.
Java Code
class Solution {
public:
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
int n = nums.size();
// left pointer
int l =0;
int res = 0;
int product = 1;
// i -> right pointer
for(int i =0;i<n;i++){
product = product * nums[i];
// keep increasing left pointer until the
// product becomes lesser than k
while(l<=i&&product>=k){
product = (int)product/nums[l];
l++;
}
//[10](1), [2],[10,2](1+2),[2,3],[3],[10,2,3](1+2+3)
res = res + (i-l+1);
}
return res;
}
};CPP Code
class Solution {
public:
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
int n = nums.size();
int l =0;
int res = 0;
int product = 1;
for(int i =0;i<n;i++){
product = product * nums[i];
while(l<=i&&product>=k){
product = (int)product/nums[l];
l++;
}
res = res + (i-l+1);
}
return res;
}
};Resources
