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.
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.
- 0 < nums.length <= 50000.
- 0 < nums[i] < 1000.
- 0 <= k < 10^6.
Credits To: leetcode.com
Leave me comments, if you have better ways to solve.
## Blog link: https://code.dennyzhang.com/subarray-product-less-than-k ## Basic Ideas: two pointers ## All nubmers are positive integers. ## So if we enlarge the window, the suarray product will increase. ## ## right pointer move one step each time ## If product of current window is less than k, get the count of possibilities. ## Otherwise move the left ## ## Complexity: class Solution: def numSubarrayProductLessThanK(self, nums, k): """ :type nums: List[int] :type k: int :rtype: int """ length = len(nums) if length == 0: return 0 res = 0 left, curProduct = 0, 1 for right in range(0, length): curProduct *= nums[right] # keep moving the left, if it's too big while left <= right and curProduct >= k: curProduct = int(curProduct/nums[left]) left += 1 # print(left, right, curProduct) if curProduct < k: # get all the possilities with nums[right] chosen res += right-left+1 return res
Original URL: https://code.dennyzhang.com/subarray-product-less-than-k