713.subarray-product-less-than-k.md

713. Subarray Product Less Than K

Clarification Questions

• k range?
• Is the input array sorted?

Test Cases

Normal Cases

Input: nums = [10, 5, 2, 8], k = 100
Output: 8

Edge / Corner Cases

• Every number is 1, but k >= 1.

Input: nums = [1, 1, 1, 1], k = 1
Output: 0

• Every number is k.

Input: nums = [2, 2, 2, 2], k = 2
Output: 0

Sliding Window

The input array is positive, so the product of any subarray will be positive and becomes greater if more elements are added. So, we can use sliding window approach to solve this problem.

• Window: The subarray that has product less than k.
• We extend our window and calculate the product, and shrink the window if the product is greater than k.

Suppose the product of subarray [X, X, X, X] < k, then the product of subarray [X, X, X] < k, which satisfies the property of sliding window. And how to calculate the number of subarrays [i..j], that would be j - i + 1.

fun numSubarrayProductLessThanK(nums: IntArray, k: Int): Int {
    // Since the range of input array is positive, there is no any product <= 1.
    if (k <= 1) return 0

    var left = 0
    var right = 0
    var count = 0
    var product = 1
    while (right < nums.size) {
        product *= nums[right]
        while (product >= k) {
            product /= nums[left]
            left++
        }
        // See below
        count += right - left + 1
        right++
    }
    return count
}

The reason for count += right - left + 1 is that we count the subarray that contains right and range from left to right. The subarray that contains 6 is

// right = 6
10, 5, 1, 6
L         R
          6
       1, 6
    5, 1, 6
10, 5, 1, 6

which is 4 subarrays, that is right - left + 1.