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.
1public class Solution {
2 public int NumSubarrayProductLessThanK(int[] nums, int k) {
3 if (k <= 1) return 0;
4 int prod = 1, count = 0, left = 0;
5 for (int right = 0; right < nums.Length; right++) {
6 prod *= nums[right];
7 while (prod >= k) prod /= nums[left++];
8 count += right - left + 1;
9 }
10 return count;
11 }
12}In C#, we implement the sliding window method to calculate the number of subarrays with a product less than k. By adjusting the window size using two pointers right and left, we efficiently count subarrays that meet the criteria.
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.
1var numSubarrayProductLessThanK_bruteforce = function(nums, k) {
2 if (k <= 1) return 0;
3 let count = 0;
4 for (let start = 0; start < nums.length; start++) {
5 let prod = 1;
6 for (let end = start; end < nums.length; end++) {
7 prod *= nums[end];
8 if (prod >= k) break;
9 count++;
10 }
11 }
12 return count;
13};The JavaScript brute force function involves checking each potential subarray product, stopping once those products are no longer below k. This complete search checks each element pairwise throughout the array.