The sliding window approach allows us to efficiently find subarrays where the product is less than k. By maintaining a window (two pointers), we can dynamically adjust the size of the current subarray based on the product of its elements. As the window size grows, the product is updated; if it exceeds k, we reduce the window from the left until the product is again less than k. This method minimizes redundant calculations.
Time Complexity: O(n) - Each element is processed at most twice.
Space Complexity: O(1) - Only a constant amount of extra space is used.
1def numSubarrayProductLessThanK(nums, k):
2 if k <= 1: return 0
3 prod = 1
4 count = left = 0
5 for right, val in enumerate(nums):
6 prod *= val
7 while prod >= k:
8 prod /= nums[left]
9 left += 1
10 count += right - left + 1
11 return countThis Python function implements the same sliding window algorithm. The product is maintained and adjusted based on the current subarray defined by the left and right pointers. The count of qualifying subarrays is incremented for each valid window.
The brute force approach involves checking every possible subarray within nums and calculating their products. Each subarray is counted if its product is less than k. Though less efficient, it guarantees correctness by examining all potential subarrays.
Time Complexity: O(n^2) - Considers all possible subarrays.
Space Complexity: O(1) - Constant extra space used.
1def numSubarrayProductLessThanK_bruteforce(nums, k):
2 if k <= 1: return 0
3 count = 0
4 for start in range(len(nums)):
5 prod = 1
6 for end in range(start, len(nums)):
7 prod *= nums[end]
8 if prod >= k:
9 break
10 count += 1
11 return countThis Python function iterates through each start position and expands the subarray to examine all subarray products. If a product reaches k, it breaks out of the loop to improve efficiency.