Problem Statement:

You 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].

Solution:

The given problem can be solved by using two pointers approach. The idea is to keep two pointers left and right to represent the left and right boundary of the subarray and then extend the subarray by moving the right pointer until the product of the subarray is less than k. When such a subarray is found, we add the count of subarrays of the current length to the result.

Initially, both the left and right pointers are set to 0. Then, we move the right pointer. For each move of the right pointer, we compute the current product, and check if it is less than k. If it is less than k, then we add the count of subarrays of the current length to the result. We continue to move the right pointer until the product of the subarray exceeds k.

When the product of the subarray exceeds k, we move the left pointer to the right, and update the product by dividing it by the element at the left pointer. We continue to move the left pointer until the product is less than k again. The count of subarrays of the current length is subtracted from the result for each move of the left pointer, since those subarrays do not have a product less than k.

Time Complexity:

The time complexity of the above algorithm is O(n), where n is the length of the input array.

Space Complexity:

The space complexity of the above algorithm is O(1), since we are storing only constant amount of information throughout the algorithm.

Code:

Here is the Python implementation of the above algorithm.

def numSubarrayProductLessThanK(nums, k): left = 0 right = 0 product = 1 count = 0

while right < len(nums):
    product *= nums[right]
    while product >= k and left <= right:
        product /= nums[left]
        left += 1
    
    count += (right - left + 1)
    right += 1
    
return count

Example:

nums = [10,5,2,6] k = 100 print(numSubarrayProductLessThanK(nums, k))

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].

1