.jpg)
Count Subarrays with Product Less Than K
Problem Statement
You are given an array arr of positive integers and an integer k.
Your task is to count the total number of contiguous subarrays whose product is strictly less than k.
Example 1
Input
arr = [10, 5, 2, 6], k = 100
Output
8
Explanation
Valid subarrays:
[10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]
Example 2
Input
arr = [1, 2, 3], k = 0
Output
0
Why This Problem Is Important
- Classic sliding window problem
- Tests understanding of two-pointer technique
- Frequently asked in Google, Amazon, Microsoft
- Works only because all numbers are positive
Approaches Overview
| Approach | Technique | Time | Space |
|---|---|---|---|
| Brute Force | Check all subarrays | O(n²) | O(1) |
| Optimal | Sliding Window | O(n) | O(1) |
Approach 1 – Brute Force
Idea
Generate all possible subarrays Compute product for each Count if product < k
Time and Space Complexity
Time: O(n²)
Space: O(1)
C++
#include
using namespace std;
int countSubarrays(vector& arr, int k){
int n = arr.size();
int count = 0;
for(int i = 0; i < n; i++){
long long prod = 1;
for(int j = i; j < n; j++){
prod *= arr[j];
if(prod < k) count++;
else break;
}
}
return count;
}
int main(){
vector arr = {10, 5, 2, 6};
int k = 100;
cout << countSubarrays(arr, k);
}
Java
class Main {
static int countSubarrays(int[] arr, int k){
int n = arr.length;
int count = 0;
for(int i = 0; i < n; i++){
long prod = 1;
for(int j = i; j < n; j++){
prod *= arr[j];
if(prod < k) count++;
else break;
}
}
return count;
}
public static void main(String[] args){
int[] arr = {10, 5, 2, 6};
int k = 100;
System.out.println(countSubarrays(arr, k));
}
}
JavaScript
function countSubarrays(arr, k){
let n = arr.length;
let count = 0;
for(let i = 0; i < n; i++){
let prod = 1;
for(let j = i; j < n; j++){
prod *= arr[j];
if(prod < k) count++;
else break;
}
}
return count;
}
// Test
console.log(countSubarrays([10,5,2,6], 100));
C#
using System;
class Program {
static int CountSubarrays(int[] arr, int k){
int n = arr.Length;
int count = 0;
for(int i = 0; i < n; i++){
long prod = 1;
for(int j = i; j < n; j++){
prod *= arr[j];
if(prod < k) count++;
else break;
}
}
return count;
}
static void Main(){
int[] arr = {10, 5, 2, 6};
int k = 100;
Console.WriteLine(CountSubarrays(arr, k));
}
}
Output
8
Approach 2- Optimal Approach (Sliding Window)
Idea
- Maintain a sliding window [left..right]
- Keep multiplying elements to product
- If product ≥ k, move left
- Number of valid subarrays ending at right = right - left + 1
Important Edge Case:
- If k ≤ 1, answer is 0
Time and Space Complexity
- Time: O(n)
- Space: O(1)
Python Implementation
def countSubarrays(arr, k):
if k <= 1:
return 0
prod = 1
left = 0
count = 0
for right in range(len(arr)):
prod *= arr[right]
while prod >= k:
prod //= arr[left]
left += 1
count += right - left + 1
return count
C++ Implementation
#include
using namespace std;
int countSubarrays(vector& arr, int k){
if(k <= 1) return 0;
long long prod = 1;
int left = 0, count = 0;
for(int right=0; right= k){
prod /= arr[left];
left++;
}
count += right - left + 1;
}
return count;
}
Java Implementation
class Main {
static int countSubarrays(int[] arr, int k){
if(k <= 1) return 0;
long prod = 1;
int left = 0, count = 0;
for(int right=0; right= k){
prod /= arr[left];
left++;
}
count += right - left + 1;
}
return count;
}
}
JavaScript Implementation
function countSubarrays(arr, k){
if(k <= 1) return 0;
let prod = 1, left = 0, count = 0;
for(let right=0; right= k){
prod /= arr[left];
left++;
}
count += right - left + 1;
}
return count;
}
C# Implementation
static int CountSubarrays(int[] arr, int k){
if(k <= 1) return 0;
long prod = 1;
int left = 0, count = 0;
for(int right=0; right= k){
prod /= arr[left];
left++;
}
count += right - left + 1;
}
return count;
}
Output
8Final Summary
| Approach | Best Use Case |
|---|---|
| Brute Force | Learning, small input |
| Sliding Window | Interview standard solution |
Next Problem in the Series
Kth Largest Element in a Stream
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.jpg)
.jpg)
.png)
