Given an array of positive integers and an integer k, find the number of contiguous subarrays where the product of all the elements is less than k.

Function Signature:

from typing import List

def num_subarray_product_less_than_k(nums: List[int], k: int) -> int:
    """
    Find the number of contiguous subarrays where the product of all elements is less than k.

    Parameters:
    - nums: List of positive integers.
    - k: Integer.

    Returns:
    - int: Number of subarrays satisfying the condition.
    """
    # Your code here

Example:

# Input: nums = [10, 5, 2, 6], k = 100
# Output: 8
# Explanation: The subarrays are [10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6].

# Input: nums = [1, 2, 3], k = 0
# Output: 0
# Explanation: There is no subarray with product less than 0.

# Input: nums = [1], k = 1
# Output: 0
# Explanation: The only element, 1, is not less than 1.

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

Note:

  • The length of the array is at most 10^5.
  • The array contains only positive integers.
  • The product of all elements in any subarray will fit in a 32-bit integer.

Instructions:

  • Write the num_subarray_product_less_than_k function to solve the problem.
  • Implement your solution in Python.
  • Provide clear comments in your code.
  • Discuss the time and space complexity of your solution.

As always, we’ll share our solution to this problem tomorrow. Stay tuned 😊