Count Contiguous Subarrays Below Threshold — Problem Statement & Solution Guide
Problem Description
Given an array of integers values and two integers n and k, count all contiguous subarrays of size n where the product of its elements is strictly less than k.
Examples
Input
[10, 5, 2, 6], n = 2, k = 200
Output
3
Explanation: Step-by-step: with input [10, 5, 2, 6], n = 2, and k = 200, we calculate the product of each subarray of size n. The subarrays are [10, 5], [5, 2], [2, 6]. Their products are 50, 10, and 12 respectively. All of these products are less than k, so the output is 3.
Input
[1, 2, 3, 4], n = 3, k = 50
Output
2
Explanation: Step-by-step: with input [1, 2, 3, 4], n = 3, and k = 50, we calculate the product of each subarray of size n. The subarrays are [1, 2, 3], [2, 3, 4]. Their products are 6 and 24 respectively. Both of these products are less than k, so the output is 2.
Constraints
- 1 <= n <= 3 * 10^4
- 1 <= arr[i] <= 1000
- 0 <= k <= 10^6
Optimal Approach & Strategy
Two pointers. Expand right, multiply product. While product >= k, divide by left element and shrink left. Number of valid subarrays ending at 'right' is (right - left + 1). Sum these up. Time O(N), Space O(1).
Brute Force Approach
Check all subarrays and multiply. Time O(N^2).
Verified Code Solutions
function countSubarrays(values, n, k) { let count = 0; for (let i = 0; i <= values.length - n; i++) { let product = 1; for (let j = i; j < i + n; j++) { product *= values[j]; } if (product < k) { count++; } } return count; }class Solution { public: int countSubarrays(vector<int>& values, int n, int k) { int count = 0; for (int i = 0; i <= values.size() - n; i++) { long long product = 1; for (int j = i; j < i + n; j++) { product *= values[j]; } if (product < k) { count++; } } return count; } };class Solution { public int countSubarrays(int[] values, int n, int k) { int count = 0; for (int i = 0; i <= values.length - n; i++) { long product = 1; for (int j = i; j < i + n; j++) { product *= values[j]; } if (product < k) { count++; } } return count; } }def countSubarrays(values, n, k): count = 0; for i in range(len(values) - n + 1): product = 1; for j in range(i, i + n): product *= values[j]; if product < k: count += 1; return countfunction countSubarrays(values, n, k) { let count = 0; for (let i = 0; i <= values.length - n; i++) { let product = 1; for (let j = i; j < i + n; j++) { product *= values[j]; } if (product < k) { count++; } } return count; }Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.