Subarrays with Sum in Range

Time: O(n)

Space: O(1)

Problem Overview

Count subarrays whose sum sits in [l, r].

Intuition

Count subarrays whose sum sits in [l, r]. With non-negative elements, sums <= X can be counted with a sliding window: for each right end, shrink the left until the window sum is at most X, then every start in [left, right] is valid. Inclusive range then equals count(sums <= r) minus count(sums <= l-1).

Algorithm

1Return solve(arr, r) - solve(arr, l - 1).
2solve(arr, x): if x < 0 return 0. Two pointers i,j with running sum s.
3For j = 0..n-1: add arr[j]; while s > x shrink from i; add (j - i + 1) to the answer.

Example Walkthrough

Input: arr = [1, 2, 3], l = 2, r = 4

1. sums <= 4: [1],[1,2],[2],[3],[1,2,3]? 6>4 so not - valid count is 4 ([1],[2],[3],[1,2]).
2. sums <= 1: only [1] -> 1.
3. Difference 4 - 1 = 3 covers [2],[1,2],[3].

Output: 3

Common Pitfalls

• This window assumes non-negative array values; negatives break monotonicity.
• Handle x < 0 in solve so l = 0 does not under-shrink.
• Add j - i + 1 before advancing j - count after an early j++ is an off-by-one.
• Empty or all-too-large cases correctly contribute 0 when the window collapses past j.

Subarrays with Sum in Range.java

Java

// Approach: Count of sums in [l, r] = (sums <= r) - (sums <= l-1). For a bound
// x, slide a window over non-negative arr: grow right, shrink left while the
// window sum exceeds x; every ending index then contributes (right-left+1)
// subarrays with sum <= x.
// Time: O(n) Space: O(1)
class Solution {

    public int countSubarray(int[] arr, int l, int r) {
        return solve(arr, r) - solve(arr, l - 1);
    }

    public static int solve(int[] arr, int x) {
        if (x < 0) {
            return 0;
        }

        int cnt = 0;
        int s = 0;
        int i = 0;
        int n = arr.length;

        for (int j = 0; j < n; j++) {
            s += arr[j];

            while (s > x && i <= j) {
                s -= arr[i];
                i++;
            }
            cnt += (j - i + 1);
        }

        return cnt;
    }
}

Was this solution helpful?