Python O(n) solution

• Idea is simple. If subarray[i, end] is smaller than k, subarray[i+1, end] will guarantee to be valid, so we can start from end position for the next element i+1, in case there is a single value greater than k, we will jump over it.
'end' in inner loop will only move forward, so complexity O(n).
Code is ugly...

``````class Solution(object):
def numSubarrayProductLessThanK(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
total = end = subtotal = 0
prod = 1
n = len(nums)
for i in xrange(n):
while end < n:
prod *= nums[end]
if prod >= k:
break
subtotal += 1
end += 1
# if we have from valid production current position to end of array,
# we can stop early with subtotal of (n+1)n/2 for the rest of array
if end == n:

prod /= nums[end]
total += subtotal

# for next element, [i+1, end] subproduction guarantee to be smaller than k
# production from next element(i+1) to end-1 is prod/nums[i]
# if end == i, we jump over the element
if i < end:
subtotal -= 1
prod /= nums[i]
else:
end += 1