Problem Statement
Given an integer array arr[] and two integers l and r, count the number of contiguous subarrays whose sum lies in the range [l, r] (inclusive).
Example
Input
arr = [1, 4, 6]
l = 3
r = 8
Output
3
Explanation
The valid subarrays are:
| Subarray | Sum |
|---|---|
| [1, 4] | 5 |
| [4] | 4 |
| [6] | 6 |
Hence, the answer is 3.
Naive Approach
The simplest way is to generate every possible subarray.
for (int i = 0; i < n; i++) {
int sum = 0;
for (int j = i; j < n; j++) {
sum += arr[j];
if (sum >= l && sum <= r)
count++;
}
}
Complexity
Time:
O(n²)Space:
O(1)
This solution is too slow for:
n = 100000
Optimized Approach
Key Observation
The constraints say:
arr[i] >= 1
All numbers are positive.
Because all elements are positive:
Expanding the window increases the sum.
Shrinking the window decreases the sum.
This property makes the Sliding Window technique possible.
Main Idea
Instead of directly counting subarrays whose sum is between l and r, we calculate:
Subarrays having
sum <= rSubarrays having
sum <= (l - 1)
Then,
Answer =
Subarrays(sum <= r)
-
Subarrays(sum <= l - 1)
Mathematically,
count(l...r)
=
count(<=r)
-
count(<l)
=
count(<=r)
-
count(<=l-1)
This is much easier to compute.
Example
arr = [2, 3, 5, 8]
l = 4
r = 13
First calculate:
count(<=13)
Then calculate:
count(<=3)
Finally,
Answer =
count(<=13)
-
count(<=3)
=
8 - 2
=
6
How Sliding Window Works
Suppose:
arr = [2, 3, 5, 8]
limit = 13
Initially,
left = 0
right = 0
sum = 0
count = 0
Step 1
Add arr[0].
sum = 2
Window:
[2]
Number of valid subarrays ending at index 0:
1
Count:
count = 1
Step 2
Move right.
sum = 2 + 3 = 5
Window:
[2, 3]
Valid subarrays ending at index 1:
[2, 3]
[3]
Total:
2
Count:
1 + 2 = 3
Step 3
Move right.
sum = 10
Window:
[2, 3, 5]
Valid subarrays:
[2, 3, 5]
[3, 5]
[5]
Three more:
count = 6
Step 4
Move right.
sum = 18
Too large:
18 > 13
Shrink the window.
Remove:
2
Now,
sum = 16
Still too large.
Remove:
3
Now,
sum = 13
Window becomes:
[5, 8]
Valid subarrays ending here:
[5, 8]
[8]
Two more.
Final count:
8
Why Do We Add count += (right - left + 1)?
Suppose:
left = 2
right = 5
Window indices:
2 3 4 5
Every valid subarray ending at right is:
arr[5]
arr[4..5]
arr[3..5]
arr[2..5]
Number of subarrays:
5 - 2 + 1
= 4
Therefore,
count += (right - left + 1);
This is the most important line in the algorithm.
Complete Code
class Solution {
public int countSubarray(int[] arr, int l, int r) {
return (int)(countAtMost(arr, r) - countAtMost(arr, l - 1));
}
private long countAtMost(int[] arr, int limit) {
// If limit is negative, no positive-sum subarray can satisfy it.
if (limit < 0)
return 0;
int left = 0;
long sum = 0;
long count = 0;
for (int right = 0; right < arr.length; right++) {
// Expand the window by including arr[right]
sum += arr[right];
// Shrink the window while the sum exceeds the limit
while (sum > limit) {
sum -= arr[left];
left++;
}
// All subarrays ending at 'right' and starting
// between 'left' and 'right' are valid.
count += (right - left + 1);
}
return count;
}
}

Join the conversation! Your thoughts help the community grow.