# 713 Subarray Product Less Than K

Your 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], [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. 1.
0 < nums.length <= 50000.
2. 2.
0 < nums[i] < 1000.
3. 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 ``. The product here is `60`, and suppose `k = 100`. The total number of subarrays that can represented here is `3` because `` we obtain the new subarrays: ``, `[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 ``, we obtain 4 new subarrays ``, `[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:
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
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 using`F(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:
# 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