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
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:
This property makes the Sliding Window technique possible.
Main Idea
Instead of directly counting subarrays whose sum is between l and r, we calculate:
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;
}
}
Code Explanation (Line by Line)
Main Function
public int countSubarray(int[] arr, int l, int r)
Receives:
Array
Lower limit
Upper limit
return (int)(countAtMost(arr, r)
- countAtMost(arr, l - 1));
Computes:
Answer =
Subarrays <= r
-
Subarrays <= l - 1
Helper Function
private long countAtMost(int[] arr, int limit)
Returns:
Number of subarrays
whose sum <= limit
if (limit < 0)
return 0;
Since every element is positive:
No subarray can have
sum <= negative number
int left = 0;
Left pointer of the sliding window.
long sum = 0;
Current window sum.
long count = 0;
Stores the answer.
for (int right = 0; right < arr.length; right++)
Expand the window one element at a time.
sum += arr[right];
Include the current element.
while (sum > limit)
If the window becomes invalid, shrink it from the left.
sum -= arr[left];
left++;
Remove the left element and move the left pointer.
count += (right - left + 1);
Count every valid subarray ending at right.
return count;
Return the total number of valid subarrays.
Dry Run
Input:
arr = [1, 4, 6]
limit = 8
| left | right | sum | count |
|---|
| 0 | 0 | 1 | 1 |
| 0 | 1 | 5 | 3 |
| 1 | 2 | 10 → 6 | 4 |
countAtMost(8) = 4
Now,
limit = 2
| left | right | sum | count |
|---|
| 0 | 0 | 1 | 1 |
| 1 | 1 | 4 → 0 | 1 |
| 2 | 2 | 6 → 0 | 1 |
countAtMost(2) = 1
Therefore,
Answer =
4 - 1
= 3
Complexity Analysis
Time Complexity
Therefore,
O(n)
Space Complexity
Only a few variables are used.
O(1)
Key Takeaways
Since all elements are positive, the Sliding Window technique is applicable.
Instead of counting sums in [l, r] directly, compute:
countAtMost(r)
countAtMost(l - 1)
The formula countAtMost(r) - countAtMost(l - 1) gives the number of subarrays with sums in the required range.
The statement count += (right - left + 1) works because, after adjusting the window, every subarray ending at right and starting from any index between left and right has a sum within the limit.
The algorithm runs in O(n) time and O(1) extra space, making it suitable for arrays of up to 10^5 elements.
Summary
This approach efficiently counts contiguous subarrays whose sums fall within a given range by leveraging the fact that all array elements are positive. Instead of checking every possible subarray, it computes the number of subarrays with sums at most r and subtracts those with sums at most l - 1. Combined with the Sliding Window technique, this yields an optimal O(n) time and O(1) extra space solution suitable for large input sizes.