Subarray Product Less Than K

Problem

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

Solution

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var numSubarrayProductLessThanK = function(nums, k) {
    let res = 0;
    let product = 1; // product of element in window
    let l = 0; // left of window
    let r = 0; // right of window

    for (; r < nums.length; r++) {
        product *= nums[r];
        while (product >= k && l <= r) {
            product /= nums[l];
            l++;
        }
        res += r - l + 1;
    }
    return res;
};

We will implement a sliding window solution. We use product to keep track of the product of elements in nums[l:r + 1]. At each iteration of incrementing r, we adjust l so that product < k. In other words, after adjusting l, nums[l:r + 1] is the largest continuous subarray of nums ending at index r with product less then k. In nums[l:r + 1], there are a total of r - l + 1 subarrays that ends at index r, hence the way we increment res. Thus, the total number of subarrays is the sum of count using the above process at every possible index r.