Simple Python solution (accepted)


  • 0
    Z
    class Solution(object):
        def numSubarrayProductLessThanK(self, nums, k):
            """
            :type nums: List[int]
            :type k: int
            :rtype: int
            """
            count = 0
            nums_len = len(nums)
            for i, val in enumerate(nums):
                if val >= k:
                    continue
                else:
                    count += 1
                j = i+1
                sum = val
                while (j < nums_len):
                    sum *= nums[j]
                    if sum >= k:
                        break
                    else:
                        count += 1
                    j+=1
            return count
    

  • 0
    H

    Brute force method would get TLE.


  • 0
    Z

    The solution was accepted as part of the contest, seems like, they added TLE test case later. Here is my revised solution with two pointers approach.

        def numSubarrayProductLessThanK(self, nums, k):
            """
            :type nums: List[int]
            :type k: int
            :rtype: int
            """
            if k <= 1:
                return 0
            
            count = 0
            nums_len = len(nums)
            left = 0
            right = 0
            product = 1
            while right < nums_len:
                product *= nums[right]
                while product >= k and left < nums_len:
                    product //= nums[left]
                    left += 1
                count += right - left + 1
                right += 1
            return count
    

Log in to reply
 

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