LeetCode 713 - Subarray Product Less Than K

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

https://leetcode.com/problems/subarray-product-less-than-k/discuss/108861/JavaC++-Clean-Code-with-Explanation

1. The idea is always keep an max-product-window less than K;
2. 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 than k again, (subarray could be empty);
3. 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: $O(N\log N)$, where $N$ is the length of nums. Inside our for loop, each binary search operation takes $O(\log N)$ time.
• Space Complexity: $O(N)$, the space used by prefix.

Because $\log(\prod_i x_i) = \sum_i \log x_i$, 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 jso 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;
    }