Double Pointer Python Soluiotn


  • 0
    A

    This is my 328ms python solution:

    class Solution(object):
        def numSubarrayProductLessThanK(self, nums, k):
            """
            :type nums: List[int]
            :type k: int
            :rtype: int
            """
            be = 0  # begin index
            ed = 0  # end index
            cur = 1 # accumulated product
            count = 0 # valid subarray
            ed = be
            n = len(nums)
            while be<n:
                while ed<n and cur*nums[ed]<k:
                    cur*=nums[ed]
                    ed+=1
                count += (ed - be)
                cur = max(cur/nums[be],1)  # corner case nums[be] >= k
                be += 1
                ed = max(be,ed) # # corner case nums[be] >= k
            return count
                
    

Log in to reply
 

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