Challenge: Count of Range Sum

• Prefix-sum reframing – any subarray sum equals the difference of two prefix sums, so a subarray sum lying in the range [lower, upper] means the left prefix lies in a shifted window relative to the right prefix.
• Merge-sort counting – embedding the pair-counting step inside the merge phase of merge sort lets you count qualifying pairs efficiently because both halves are already sorted.
• Pointer sliding – for each right-half prefix, two pointers slide over the sorted left half to find the range of qualifying left prefixes, giving linear work per merge level.
• O(n log n) total – the log n merge levels each contribute O(n) counting work, plus O(n) merging work.
• Overflow safety – prefix sums must use long because subtracting the bounds from accumulated sums can exceed int range on monetary data.

What is the Count of Range Sum problem?

The problem gives you an array of integers (possibly negative), and two bounds lower and upper. You must count how many contiguous subarrays have a sum that falls within the inclusive range [lower, upper]. The brute-force approach of checking every subarray is O(n^2), which is too slow for large inputs.

package com.bank.compliance;

public class RangeSumCounter {

    // Brute force: O(n^2) - too slow for production
    public static int countBrute(int[] flows, int lower, int upper) {
        int count = 0;
        for (int i = 0; i < flows.length; i++) {
            long sum = 0;
            for (int j = i; j < flows.length; j++) {
                sum += flows[j];
                if (sum >= lower && sum <= upper) count++;
            }
        }
        return count;
    }
}

Why do prefix sums help?

Let P[0] = 0 and P[i] = sum of the first i elements. The sum of the subarray from index j to index i-1 is P[i] - P[j]. We want to count pairs (j, i) where j < i and lower <= P[i] - P[j] <= upper. Rearranging, for each right index i, we need the count of left indices j where P[i] - upper <= P[j] <= P[i] - lower. This reframing turns the problem into counting pairs in a sorted structure.

package com.bank.compliance;

public class PrefixSumDemo {

    public static void showPrefixSums() {
        int[] flows = {-2, 5, -1};
        // P[0]=0, P[1]=-2, P[2]=3, P[3]=2
        // Subarray [0,0]: P[1]-P[0] = -2
        // Subarray [0,1]: P[2]-P[0] = 3
        // Subarray [1,1]: P[2]-P[1] = 5
        // Subarray [0,2]: P[3]-P[0] = 2
        // Subarray [1,2]: P[3]-P[1] = 4
        // Subarray [2,2]: P[3]-P[2] = -1
        // For range [-2, 2], qualifying: -2, 2, -1 => count = 3
        System.out.println("Qualifying subarrays: 3");
    }
}

How does the merge-sort counting technique work?

We embed the pair-counting step inside a merge sort over the prefix-sum array. During each merge step, the left half and right half are each sorted. For each prefix value in the right half, we slide two pointers over the left half to count how many left values fall into the required shifted interval. Because both halves are sorted, these pointer scans are linear per merge level.

package com.bank.compliance;

public class MergeSortRangeSum {

    public static int countRangeSum(int[] flows, int lower, int upper) {
        int n = flows.length;
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + flows[i];
        }
        long[] temp = new long[n + 1];
        return mergeCount(prefix, temp, 0, n, lower, upper);
    }

    private static int mergeCount(long[] p, long[] temp, int lo, int hi, int lower, int upper) {
        if (lo >= hi) return 0;
        int mid = lo + (hi - lo) / 2;
        int count = mergeCount(p, temp, lo, mid, lower, upper)
                  + mergeCount(p, temp, mid + 1, hi, lower, upper);

        // Count qualifying pairs across left and right halves
        int j1 = mid + 1, j2 = mid + 1;
        for (int i = lo; i <= mid; i++) {
            while (j1 <= hi && p[j1] - p[i] < lower) j1++;
            while (j2 <= hi && p[j2] - p[i] <= upper) j2++;
            count += j2 - j1;
        }

        // Standard merge to keep the array sorted
        System.arraycopy(p, lo, temp, lo, hi - lo + 1);
        int left = lo, right = mid + 1, idx = lo;
        while (left <= mid && right <= hi) {
            if (temp[left] <= temp[right]) p[idx++] = temp[left++];
            else p[idx++] = temp[right++];
        }
        while (left <= mid) p[idx++] = temp[left++];
        while (right <= hi) p[idx++] = temp[right++];

        return count;
    }
}

How do the two pointers slide during the merge?

For each prefix value P[i] in the left half, we advance pointer j1 over the right half while P[j1] - P[i] < lower (too small), and advance pointer j2 while P[j2] - P[i] <= upper (still in range). The count of qualifying right-half prefixes for this left-half prefix is j2 - j1. Because the left half is sorted and both pointers only move forward, the total pointer work across all left-half elements is linear.

// Pointer sliding example:
// Left half (sorted):  [0, 2, 3]
// Right half (sorted): [1, 4, 5]
// lower=1, upper=3
//
// For P[i]=0: need right values in [0+1, 0+3] = [1, 3]
//   j1 finds 1, j2 finds past 1 (next is 4 > 3), count += 1
// For P[i]=2: need right values in [2+1, 2+3] = [3, 5]
//   j1 finds 4, j2 finds past 5, count += 2
// For P[i]=3: need right values in [3+1, 3+3] = [4, 6]
//   j1 finds 4, j2 finds past 5, count += 2

Why use long for prefix sums?

When the array contains monetary values near Integer.MAX_VALUE or Integer.MIN_VALUE, the prefix sums and their differences can overflow a 32-bit int. In banking, transaction amounts can be large, and subtracting bounds from accumulated sums can push values far beyond int range. Always use long for prefix sums.

package com.bank.compliance;

public class OverflowSafety {

    public static void showRisk() {
        int[] amounts = {Integer.MAX_VALUE, Integer.MAX_VALUE};
        // int prefix would overflow: 2147483647 + 2147483647 = -2 (wrong!)
        // long prefix: 2147483647L + 2147483647L = 4294967294L (correct)
        long prefix = (long) amounts[0] + amounts[1];
        System.out.println("Safe prefix sum: " + prefix);
    }
}

What is the alternative Fenwick tree approach?

Instead of merge sort, you can coordinate-compress the prefix values and use a Fenwick tree (Binary Indexed Tree) to count how many previous prefix values fall in the required range for each new prefix. This is also O(n log n) but uses a different data structure. Some interviewers prefer this approach because it avoids the complexity of modifying merge sort.

// Fenwick tree approach outline:
// 1. Build prefix sums
// 2. Coordinate-compress all prefix values and their shifted bounds
// 3. For each prefix P[i] from left to right:
//    a. Query Fenwick tree for count in [P[i]-upper, P[i]-lower]
//    b. Insert P[i] into Fenwick tree
// 4. Total query results = answer

What are edge cases to watch for?

The array can contain all negative values, all positive values, or a mix. The bounds lower and upper can be negative. A single-element subarray is valid. An empty array should return zero. The prefix sum at index zero is zero, which means the entire prefix up to any index is also a valid subarray.

package com.bank.compliance;

public class EdgeCases {

    public static void test() {
        // All negative: flows = {-3, -2, -1}, lower=-5, upper=-2
        // Subarrays: -3, -5, -6, -2, -3, -1
        // In range [-5,-2]: -3, -5, -2, -3 => count = 4

        // Single element: flows = {5}, lower=5, upper=5
        // Only subarray sum is 5, which is in range => count = 1

        // Empty: flows = {}, any bounds => count = 0
        System.out.println("Edge cases handled");
    }
}

What is the time and space complexity?

| Approach | Time | Space | Notes |
|---|---|---|---|
| Brute force | O(n^2) | O(1) | Check every subarray |
| Merge-sort counting | O(n log n) | O(n) | Prefix array + merge buffer |
| Fenwick tree | O(n log n) | O(n) | Coordinate compression + BIT |
| Balanced BST | O(n log n) | O(n) | TreeMap-based counting |

The merge-sort approach is the most self-contained and does not require knowledge of Fenwick trees or balanced BSTs, which is why it is the preferred interview answer.

What should a senior engineer know?

A senior engineer should recognize that this is a hard-tier problem that fuses prefix sums with order-statistics counting. The key insight is that the counting can ride along inside a merge sort because the sorted halves allow efficient range queries with sliding pointers. The divide-and-conquer structure preserves the ordering semantics: we only count pairs where the right index came from a position after the left index. Mentioning both the merge-sort and Fenwick approaches shows depth, and flagging the long overflow safeguard shows production awareness.

// Senior checklist:
// 1. Recognize prefix-sum reframing instantly
// 2. Know that merge-sort embeds the count in the merge phase
// 3. Explain why pointer sliding is linear per merge level
// 4. Mention Fenwick tree as an alternative
// 5. Use long prefix sums for overflow safety
// 6. Handle edge cases: empty array, single element, all negatives