https://leetcode.com/problems/subarray-product-less-than-k/solution/
Your are given an array of positive integers
nums
.
Count and print the number of (contiguous) subarrays where the product of all the elements in the subarray is 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.
Note:
0 < nums.length <= 50000
.0 < nums[i] < 1000
.0 <= k < 10^6
.Sliding Window
- The idea is always keep an
max-product-window
less thanK
; - Every time shift window by adding a new number on the right(
j
), if the product is greater than k, then try to reduce numbers on the left(i
), until the subarray product fit less thank
again, (subarray could be empty); - Each step introduces
x
new subarrays, where x is the size of the current window(j + 1 - i)
;
example:
for window (5, 2), when 6 is introduced, it add 3 new subarray: (5, (2, (6)))
(6)
(2, 6)
(5, 2, 6)
For each
right
, call opt(right)
the smallest left
so that the product of the subarray nums[left] * nums[left + 1] * ... * nums[right]
is less than k
. opt
is a monotone increasing function, so we can use a sliding window.
Algorithm
Our loop invariant is that
left
is the smallest value so that the product in the window prod = nums[left] * nums[left + 1] * ... * nums[right]
is less than k
.
For every right, we update
left
and prod
to maintain this invariant. Then, the number of intervals with subarray product less than k
and with right-most coordinate right
, is right - left + 1
. We'll count all of these for each value of right
.public int numSubarrayProductLessThanK(int[] nums, int k) { if (k <= 1) return 0; int prod = 1, ans = 0, left = 0; for (int right = 0; right < nums.length; right++) { prod *= nums[right]; while (prod >= k) prod /= nums[left++]; ans += right - left + 1; } return ans; }
public int numSubarrayProductLessThanK(int[] nums, int k) {
ArrayDeque<Integer> queue = new ArrayDeque<>();
long curProduct = 1;
long result = 0;
for (int i = 0; i < nums.length; i++) {
int num = nums[i];
boolean added = false;
if (curProduct * num < k) {
added = true;
curProduct *= num;
queue.addLast(num);
} else {
int count = 0;
while (!queue.isEmpty() && curProduct * num >= k) {
count++;
curProduct /= queue.peekFirst();
queue.removeFirst();
}
result += getSubarrayCount(count, queue.size());
}
if (!added && curProduct * num < k) {
queue.addLast(num);
curProduct *= num;
}
}
result += (long) queue.size() * (1 + queue.size()) / 2;
if (result >= Integer.MAX_VALUE) {
result = Integer.MAX_VALUE;
}
return (int) result;
}
private long getSubarrayCount(long count, long remaingingSize) {
return (1 + count) * count / 2 + count * remaingingSize;
}
Binary Search on Logarithms
- Time Complexity: , where is the length of
nums
. Inside our for loop, each binary search operation takes time. - Space Complexity: , the space used by
prefix
.
Because , we can reduce the problem to subarray sums instead of subarray products. The motivation for this is that the product of some arbitrary subarray may be way too large (potentially
1000^50000
), and also dealing with sums gives us some more familiarity as it becomes similar to other problems we may have solved before.
Algorithm
After this transformation where every value
x
becomes log(x)
, let us take prefix sums prefix[i+1] = nums[0] + nums[1] + ... + nums[i]
. Now we are left with the problem of finding, for each i
, the largest j
so that nums[i] + ... + nums[j] = prefix[j] - prefix[i] < k
.
Because
prefix
is a monotone increasing array, this can be solved with binary search. We add the width of the interval [i, j]
to our answer, which counts all subarrays [i, k]
with k <= j
.public int numSubarrayProductLessThanK(int[] nums, int k) { if (k == 0) return 0; double logk = Math.log(k); double[] prefix = new double[nums.length + 1]; for (int i = 0; i < nums.length; i++) { prefix[i+1] = prefix[i] + Math.log(nums[i]); } int ans = 0; for (int i = 0; i < prefix.length; i++) { int lo = i + 1, hi = prefix.length; while (lo < hi) { int mi = lo + (hi - lo) / 2; if (prefix[mi] < prefix[i] + logk - 1e-9) lo = mi + 1; else hi = mi; } ans += lo - i - 1; } return ans; }