713. Subarray Product Less Than K #

Problem #

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.

Example 1:

Input: nums = [10, 5, 2, 6], k = 100
Output: 8
Explanation: The 8 subarrays that have product less than 100 are: [10], [5], [2], [6], [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.

Note:

• 0 < nums.length <= 50000.
• 0 < nums[i] < 1000.
• 0 <= k < 10^6.

Problem Summary #

Given an array, output the number of windows that meet the condition that the product of all numbers in the window is less than K.

Solution Idea #

This problem is also a sliding window problem. During the sliding process of the window, continuously multiply the elements until the product is greater than k. When it is greater than k, shrink the left side of the window. There is another case that needs to be handled separately, namely cases like [100]. In this case, the product in the window equals k and is not less than k; the left side of the window equals the right side. At this time, both the left and right sides of the window need to move right simultaneously.

Code #

package leetcode

func numSubarrayProductLessThanK(nums []int, k int) int {
	if len(nums) == 0 {
		return 0
	}
	res, left, right, prod := 0, 0, 0, 1
	for left < len(nums) {
		if right < len(nums) && prod*nums[right] < k {
			prod = prod * nums[right]
			right++
		} else if left == right {
			left++
			right++
		} else {
			res += right - left
			prod = prod / nums[left]
			left++
		}
	}
	return res
}