Count of Range Sum

Given an integer array nums and two integers lower and upper, return the number of range sums that lie in [lower, upper] inclusive.

Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j inclusive, where i <= j.

Example 1:

Input: nums = [-2,5,-1], lower = -2, upper = 2 Output: 3 Explanation: The three ranges are: [0,0], [2,2], and [0,2] and their respective sums are: -2, -1, 2.

Example 2:

Input: nums = [0], lower = 0, upper = 0 Output: 1

Constraints:

• 1 <= nums.length <= 105
• -231 <= nums[i] <= 231 - 1
• -105 <= lower <= upper <= 105
• The answer is guaranteed to fit in a 32-bit integer.

Approach: Merge Sort on Prefix Sums (Divide and Conquer)

Algorithm

1. Build the prefix sum array prefix where prefix[i] is the sum of nums[0..i-1], so S(i, j) = prefix[j+1] - prefix[i]
2. The count is the number of pairs (i, j) with i < j and lower <= prefix[j] - prefix[i] <= upper
3. Merge sort the prefix sums; while merging, for every left element prefix[i], count how many right elements prefix[j] fall into the window [prefix[i] + lower, prefix[i] + upper]
4. Because the right half is sorted, a two-pointer window finds that count in linear time per merge step
5. Sum the counts across all merge steps; the sorted order also makes the comparison of halves valid

Time & Space Complexity

• Time Complexity: O(n log n) - merge sort plus linear counting per merge
• Space Complexity: O(n) - the prefix array and temporary merge array

Java Implementation

public class CountOfRangeSum {

    private int lower;
    private int upper;
    private int count;

    public int countRangeSum(int[] nums, int lower, int upper) {
        this.lower = lower;
        this.upper = upper;
        this.count = 0;

        long[] prefix = new long[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }

        mergeSort(prefix, new long[prefix.length], 0, prefix.length - 1);
        return count;
    }

    private void mergeSort(long[] sums, long[] temp, int lo, int hi) {
        if (lo >= hi) {
            return;
        }
        int mid = lo + (hi - lo) / 2;
        mergeSort(sums, temp, lo, mid);
        mergeSort(sums, temp, mid + 1, hi);

        int l = mid + 1;
        int r = mid + 1;
        for (int i = lo; i <= mid; i++) {
            while (l <= hi && sums[l] - sums[i] < lower) {
                l++;
            }
            while (r <= hi && sums[r] - sums[i] <= upper) {
                r++;
            }
            count += r - l;
        }

        int p = lo;
        int q = mid + 1;
        int k = lo;
        while (p <= mid && q <= hi) {
            if (sums[p] <= sums[q]) {
                temp[k++] = sums[p++];
            } else {
                temp[k++] = sums[q++];
            }
        }
        while (p <= mid) {
            temp[k++] = sums[p++];
        }
        while (q <= hi) {
            temp[k++] = sums[q++];
        }
        System.arraycopy(temp, lo, sums, lo, hi - lo + 1);
    }

    // Test method
    public static void main(String[] args) {
        CountOfRangeSum solver = new CountOfRangeSum();
        int[] nums1 = {-2, 5, -1};
        System.out.println("countRangeSum([-2,5,-1], -2, 2): " + solver.countRangeSum(nums1, -2, 2)); // Expected: 3

        solver = new CountOfRangeSum();
        int[] nums2 = {0};
        System.out.println("countRangeSum([0], 0, 0): " + solver.countRangeSum(nums2, 0, 0)); // Expected: 1
    }
}

Example Walkthrough

For nums = [-2, 5, -1], lower = -2, upper = 2:

1. Prefix sums: [0, -2, 3, 2]
2. Range sums correspond to pairs: (0,0) -> -2, (1,1) -> 5, (2,2) -> -1, (0,1) -> 3, (1,2) -> 4, (0,2) -> 2
3. Filtering to [-2, 2] keeps -2, -1, and 2: a total of 3 valid ranges

Key Points

1. Prefix Sum Reduction: S(i, j) = prefix[j+1] - prefix[i] turns range sums into pair differences
2. Divide and Conquer: Counting cross-half pairs happens during the merge step
3. Sorted Right Half: Since the right half is sorted, a sliding window finds all valid prefix[j] in O(n)
4. Long Prefix Sums: Use long because -2^31 <= nums[i] <= 2^31 - 1 can overflow int
5. O(n log n): The merge sort improves on the O(n²) brute-force pair enumeration