Count of Range Sum

Count of Range Sum

What is this problem about?

The "Count of Range Sum interview question" is an advanced data structure problem that involves analyzing the sums of continuous sub-segments within an array. You are given an integer array and a range defined by lower and upper bounds. Your task is to find the total number of subarrays whose sum falls inclusively within this range. While calculating subarray sums is simple, doing so efficiently for large arrays requires a deeper understanding of prefix sums and optimized search structures.

Why is this asked in interviews?

Companies like Google, Meta, and Amazon ask the "Count of Range Sum coding problem" because it tests a candidate's ability to optimize a brute-force $O(N^2)$ approach into something much faster, typically $O(N \log N)$. It evaluates proficiency in advanced concepts like Merge Sort variations, Segment Trees, or Binary Indexed Trees. It is a true "Hard" level question that separates candidates based on their algorithmic depth and ability to handle complex range-based queries.

Algorithmic pattern used

This problem is most commonly solved using the Divide and Conquer pattern, specifically a variation of the Merge Sort algorithm.

1. Prefix Sums: Convert the array into a prefix sum array. The sum of any subarray $[i, j]$ can be calculated as prefixSum[j+1] - prefixSum[i].
2. The Condition: We need to find pairs $(i, j)$ such that $lower \leq prefixSum[j] - prefixSum[i] \leq upper$, which translates to $prefixSum[j] - upper \leq prefixSum[i] \leq prefixSum[j] - lower$.
3. Merge Sort: During the merge step of the prefix sum array, for each element in the right half, we count how many elements in the left half satisfy the range condition. Since both halves are sorted during the process, we can use two pointers to find these counts in linear time for each merge step.

Example explanation

Suppose we have an array [3, -1, 2], with lower = 1 and upper = 2.

1. Prefix Sums: [0, 3, 2, 4].
2. Subarray Analysis:
   • [3] (sum 3) -> Outside range.
   • [-1] (sum -1) -> Outside range.
   • [2] (sum 2) -> Inside range.
   • [3, -1] (sum 2) -> Inside range.
   • [-1, 2] (sum 1) -> Inside range.
   • [3, -1, 2] (sum 4) -> Outside range. Total count: 3. The algorithm efficiently counts these using the sorted prefix sums without checking every pair individually.

Common mistakes candidates make

• Brute Force: Trying to use nested loops to calculate all subarray sums ($O(N^2)$), which will time out on large inputs.
• Ignoring Prefix Sums: Attempting to solve the problem directly on the original array rather than transforming it into a prefix sum problem.
• Integer Overflow: Forgetting that subarray sums can exceed the range of a 32-bit integer, requiring long types in many languages.

Interview preparation tip

Master the "Merge Sort interview pattern" for counting problems. This technique is also used in "Inversion Count" and "Count of Smaller Numbers After Self." If you can explain how sorting sub-segments helps in counting range-based pairs, you will demonstrate high-level algorithmic reasoning.