713 Subarray Product Less Than K

Your are given an array of positive integersnums.

Count and print the number of (contiguous) subarrays where the product of all the elements in the subarray is less thank.

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.

Note:

1. 0 < nums.length <= 50000.

2. 0 < nums[i] < 1000.

3. 0 <= k < 10^6.

The Idea: Keep two pointers, left and right that represent the a current product that is less than k. The right point will always increment 1 at a time and multiply the underlying number, and the left point will adjust the window by moving left and dividing the underlying number to represent the subarray product. The distance between left and right (length of the subarray) will also represent the number of subarrays that have a product less than k. To understand this consider our current subarray to be [5,2], and the right point just added [6]. The product here is 60, and suppose k = 100. The total number of subarrays that can represented here is 3 because [6] we obtain the new subarrays: [6], [2,6], and [5,2,6]. that is, the new element that the right pointed added can become a part of every element before it in the subarray product, including just itself. Another example: prev: [5,2,4] and [6], we obtain 4 new subarrays [6], [4,6], [2,4,6], and [5,2,4,6].

Complexity: O(n) time and constant space

class Solution:
    def numSubarrayProductLessThanK(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        total_less_k = 0
        if not nums or k <= 1:
            return total_less_k

        product = 1
        total, left = 0, 0
        for right, num in enumerate(nums):
            product *= num
            while left < len(nums) and product >= k:
                product /= nums[left]
                left += 1
            total += right - left + 1
        return total

Limited n^2 Solution

This solution is limited in the sense of the float datatype capacity. What we do is first create a cumulative product array and then check all subarrays by looking at the left and right boundaries of this array and see if the product of the subarray exceeds k. This is analogous to finding the sum from a to b in a discrete array usingF(b) - F(a-1). With a cumulative product, we can find the product of a subarray by doing F(b) / F(a-1).

class Solution:
    def numSubarrayProductLessThanK(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        total_less_k = 0
        if not nums:
            return total_less_k

        # modify to cumulative product
        for i in range(1, len(nums)):
            nums[i] = nums[i] * nums[i-1]

        # to make things a bit more efficient
        # iterate along where start == 0
        for num in nums:
            if num < k:
                total_less_k += 1

        # now iterate through upper right of matrix
        for start in range(1, len(nums)):
            for end in range(start, len(nums)):
                if nums[end] / nums[start - 1]:
                    total_less_k += 1

        return total_less_k