Given an array of integers nums and an integer k, return the number of contiguous subarrays where the product of all the elements in the subarray is strictly 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.
Example 2:
Input: nums = [1,2,3], k = 0 Output: 0
Constraints:
1 <= nums.length <= 3 * 1041 <= nums[i] <= 10000 <= k <= 106The 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.
The solution leverages a sliding window (or two-pointer) technique. The product of elements within the window is maintained, and pointers left and right are used to denote the current subarray. If the product exceeds k, the left pointer is moved to shrink the window until the product is less than k. The count of subarrays ending at each index is added to the total count.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) - Each element is processed at most twice.
Space Complexity: O(1) - Only a constant amount of extra space is used.
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.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2) - Considers all possible subarrays.
Space Complexity: O(1) - Constant extra space used.
| Approach | Complexity |
|---|---|
| Sliding Window Approach | Time Complexity: |
| Brute Force Approach | Time Complexity: |
LeetCode 713. Subarray Product Less Than K (Algorithm Explained) • Nick White • 36,500 views views
Watch 9 more video solutions →Practice Subarray Product Less Than K with our built-in code editor and test cases.
Practice on FleetCode