Here’s a Python implementation of the num_subarray_product_less_than_k function. This solution uses a sliding window approach to efficiently count the number of contiguous subarrays with a product less than k.

from typing import List

def num_subarray_product_less_than_k(nums: List[int], k: int) -> int:
    if k <= 1:
        return 0

    # Initialize variables
    product = 1
    count = 0
    left = 0

    # Iterate through the array using a sliding window
    for right in range(len(nums)):

        # Update the product with the current number
        product *= nums[right]

        while product >= k:
            # Shrink the window from the left
            product /= nums[left]
            left += 1

        # Every subarray ending at the current right pointer is valid
        # Update the count with the number of subarrays in the current window
        count += (right - left + 1)

    return count

# Example usage:
nums = [10, 5, 2, 6]
k = 100
result = num_subarray_product_less_than_k(nums, k)
print(result)  # Output: 8

nums = [1, 2, 3]
k = 0
result = num_subarray_product_less_than_k(nums, k)
print(result)  # Output: 0

nums = [1]
k = 1
result = num_subarray_product_less_than_k(nums, k)
print(result)  # Output: 0

nums = [2]
k = 2
result = num_subarray_product_less_than_k(nums, k)
print(result)  # Output: 0

Explanation:

  • We initialize count to keep track of the number of subarrays and product to keep track of the product of elements within the window.
  • We use a sliding window approach, where left and right pointers define the window boundaries.
  • We iterate through the array using the right pointer, updating the product and expanding the window.
  • Whenever the product exceeds k, we shrink the window from the left until the product is less than k again.
  • At each step, we count the number of subarrays in the current window and update the count variable.
  • Finally, we return the total count of subarrays that satisfy the condition.

Time Complexity:

The time complexity of this solution is O(N), where N is the length of the input array. We iterate through the array once using the sliding window approach.

Space Complexity:

The space complexity is O(1) because we are using only a constant amount of extra space regardless of the input size.