Sponsored
Sponsored
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.
1#include <vector>
2using namespace std;
3
4int numSubarrayProductLessThanK(vector<int>& nums, int k) {
5 if (k <= 1) return 0;
6 int prod = 1, count = 0, left = 0;
7 for (int right = 0; right < nums.size(); right++) {
8 prod *= nums[right];
9 while (prod >= k) prod /= nums[left++];
10 count += right - left + 1;
11 }
12 return count;
13}This C++ solution also uses the sliding window technique. The vector nums is traversed using a for loop. A product of the elements between the left and right indices is maintained. The window is adjusted whenever needed by increasing left to ensure the product remains less than k.
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.
1
This C function explores all subarrays starting from each index and computes their products. It stops extending a subarray when its product reaches or exceeds k, thereby optimizing to some degree compared to recalculating products from scratch for each subarray.