713. Subarray Product Less Than K Medium

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

Approach

Input: An integer array nums and an integer k

Output: Return the number of contiguous subarrays where the product of elements is strictly less than k

This problem falls under the Variable-length Sliding Window category.

We need to use two pointers to maintain the size of a window, and another variable product to track the product within the window.

When product >= k, it implies the window condition is no longer met, so we must move the left boundary to shrink the window and update the new product.

Each time we move the right boundary to expand the window, as long as the condition is satisfied, we update the answer: count += (right - left) + 1.

The term (right - left) + 1 represents all valid subarrays ending exactly at right.

Implementation

python

from typing import List

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        # If k is less than or equal to 1, all products will be >= k (since array has positive integers), so return 0 directly
        if k <= 1:
            return 0

        left = 0             # Left boundary of the sliding window
        product = 1          # The product within the current window
        count = 0            # Number of subarrays satisfying the condition

        # Iterate over the array, where right is the right boundary of the window
        for right, num in enumerate(nums):
            product *= num   # Include the current element into the product

            # If the product is >= k, move left boundary until the product is strictly less than k again
            while product >= k and left <= right:
                product //= nums[left]
                left += 1

            # All subarrays ending at 'right' within the current window satisfy product < k
            count += (right - left + 1)

        return count

javascript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var numSubarrayProductLessThanK = function(nums, k) {
    if (k <= 1) return 0;

    let left = 0;
    let count = 0;
    let product = 1;

    for (let right = 0; right < nums.length; right++) {
        product *= nums[right];

        while (product >= k) {
            product /= nums[left];
            left++;
        }

        count += (right - left) + 1;
    }

    return count;
};

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

Links

713. Subarray Product Less Than K (English)713. 乘积小于 K 的子数组 (Chinese)