Python O(n) solution


  • 0
    S

    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:
                    return total + (subtotal+1)*subtotal/2
                
                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
            return total 
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.