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

Code
arr = [1, 4, 6]
l = 3
r = 8

Output

Code
3

Explanation

The valid subarrays are:

SubarraySum
[1, 4]5
[4]4
[6]6

Hence, the answer is 3.

Naive Approach

The simplest way is to generate every possible subarray.

Java
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:

Code
n = 100000

Optimized Approach

Key Observation

The constraints say:

Code
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,

Code
Answer =
Subarrays(sum <= r)
-
Subarrays(sum <= l - 1)

Mathematically,

Code
count(l...r)
=
count(<=r)
-
count(<l)

=
count(<=r)
-
count(<=l-1)

This is much easier to compute.

Example

Code
arr = [2, 3, 5, 8]

l = 4
r = 13

First calculate:

Code
count(<=13)

Then calculate:

Code
count(<=3)

Finally,

Code
Answer =
count(<=13)
-
count(<=3)

=
8 - 2

=
6

How Sliding Window Works

Suppose:

Code
arr = [2, 3, 5, 8]

limit = 13

Initially,

Code
left = 0
right = 0
sum = 0
count = 0

Step 1

Add arr[0].

Code
sum = 2

Window:

Code
[2]

Number of valid subarrays ending at index 0:

Code
1

Count:

Code
count = 1

Step 2

Move right.

Code
sum = 2 + 3 = 5

Window:

Code
[2, 3]

Valid subarrays ending at index 1:

Code
[2, 3]
[3]

Total:

Code
2

Count:

Code
1 + 2 = 3

Step 3

Move right.

Code
sum = 10

Window:

Code
[2, 3, 5]

Valid subarrays:

Code
[2, 3, 5]
[3, 5]
[5]

Three more:

Code
count = 6

Step 4

Move right.

Code
sum = 18

Too large:

Code
18 > 13

Shrink the window.

Remove:

Code
2

Now,

Code
sum = 16

Still too large.

Remove:

Code
3

Now,

Code
sum = 13

Window becomes:

Code
[5, 8]

Valid subarrays ending here:

Code
[5, 8]
[8]

Two more.

Final count:

Code
8

Why Do We Add count += (right - left + 1)?

Suppose:

Code
left = 2
right = 5

Window indices:

Code
2 3 4 5

Every valid subarray ending at right is:

Code
arr[5]
arr[4..5]
arr[3..5]
arr[2..5]

Number of subarrays:

Code
5 - 2 + 1

= 4

Therefore,

Java
count += (right - left + 1);

This is the most important line in the algorithm.

Complete Code

Java
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

Java
public int countSubarray(int[] arr, int l, int r)

Receives:

Java
return (int)(countAtMost(arr, r)
            - countAtMost(arr, l - 1));

Computes:

Code
Answer =
Subarrays <= r
-
Subarrays <= l - 1

Helper Function

Java
private long countAtMost(int[] arr, int limit)

Returns:

Code
Number of subarrays
whose sum <= limit
Java
if (limit < 0)
    return 0;

Since every element is positive:

Code
No subarray can have
sum <= negative number
Java
int left = 0;

Left pointer of the sliding window.

Java
long sum = 0;

Current window sum.

Java
long count = 0;

Stores the answer.

Java
for (int right = 0; right < arr.length; right++)

Expand the window one element at a time.

Java
sum += arr[right];

Include the current element.

Java
while (sum > limit)

If the window becomes invalid, shrink it from the left.

Java
sum -= arr[left];
left++;

Remove the left element and move the left pointer.

Java
count += (right - left + 1);

Count every valid subarray ending at right.

Java
return count;

Return the total number of valid subarrays.

Dry Run

Input:

Code
arr = [1, 4, 6]

limit = 8
leftrightsumcount
0011
0153
1210 → 64
Code
countAtMost(8) = 4

Now,

Code
limit = 2
leftrightsumcount
0011
114 → 01
226 → 01
Code
countAtMost(2) = 1

Therefore,

Code
Answer =
4 - 1

= 3

Complexity Analysis

Time Complexity

Therefore,

Code
O(n)

Space Complexity

Only a few variables are used.

Code
O(1)

Key Takeaways

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.