Count of Range Sum [Hard] — Prefix Sum + Merge Sort Explained for Interviews

Problem Statement#

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

A range sum sum(i, j) is defined as nums[i] + nums[i+1] + ... + nums[j] where 0 <= i <= j <= n - 1.

Examples:

Input:  nums = [-2, 5, -1],  lower = -2,  upper = 2
Output: 3
Explanation: The three valid ranges are [0,0] → -2, [2,2] → -1, [0,2] → 2.
 
Input:  nums = [0],  lower = 0,  upper = 0
Output: 1

Constraints:

• 1 <= nums.length <= 10^5
• -2^31 <= nums[i] <= 2^31 - 1
• -10^5 <= lower <= upper <= 10^5
• The answer is guaranteed to fit in a 32-bit integer.

Why This Problem Matters#

Count of Range Sum (LeetCode 327) is rated Hard, and it deserves that rating — not because the code is long, but because arriving at the efficient solution requires connecting three separate ideas: prefix sums, the inversion-count pattern from merge sort, and two-pointer range counting. Each idea alone is a standard interview topic. The insight is realising they compose together.

This problem has appeared in Google and Amazon on-site rounds, and it belongs to a cluster of "count pairs satisfying a condition across an array" problems that show up repeatedly at top companies:

• LC 315 — Count of Smaller Numbers After Self: count pairs (i, j) with i < j and nums[j] < nums[i].
• LC 493 — Reverse Pairs: count pairs (i, j) with i < j and nums[i] > 2 * nums[j].
• LC 327 — Count of Range Sum (this problem): count pairs of indices (i, j) where the subarray sum falls inside a range.

All three problems share the same skeleton: sort while counting, using merge sort to gain the ordering you need without losing the relationship between elements. Mastering one gives you the template for the others.

Beyond interviews, the problem deepens your understanding of how prefix sums turn subarray-sum queries into point-lookup problems, and how divide-and-conquer can count structured pairs in O(n log n) time where naive enumeration costs O(n^2).

The Prefix Sum + Merge Sort Insight#

Step 1 — Translate subarray sums into prefix differences#

Define the prefix sum array P where:

P[0] = 0
P[k] = nums[0] + nums[1] + ... + nums[k-1]

Then sum(i, j) = P[j+1] - P[i]. The problem becomes: count pairs (i, j) with i < j+1 (equivalently i <= j) such that:

lower <= P[j+1] - P[i] <= upper

Rename indices: let b = j+1 and a = i, where 0 &lt;= a < b &lt;= n. We need:

lower <= P[b] - P[a] <= upper

which rearranges to:

P[b] - upper <= P[a] <= P[b] - lower

So for every index b in the prefix array, we want to count how many earlier indices a (with a < b) have P[a] in the window [P[b] - upper, P[b] - lower].

Step 2 — Why sorting helps#

If we could maintain the prefix values seen so far in sorted order, we could binary-search for the window [P[b] - upper, P[b] - lower] in O(log n) per query — giving O(n log n) total. A Binary Indexed Tree (BIT) or balanced BST does exactly this.

But there is a cleaner approach using the structure we already know: merge sort.

Step 3 — Counting during merge#

Merge sort divides the prefix array into two halves, sorts each recursively, and merges. The crucial observation:

When merging the left half (already sorted) and the right half (already sorted), every element of the right half came from a later index than every element of the left half in the original array.

So during the merge step, for each P[b] in the right half, we count how many P[a] values in the left half satisfy P[b] - upper <= P[a] <= P[b] - lower. Because both halves are sorted, we can do this with two pointers that never move backwards — one pointer lo for the left boundary and one pointer hi for the right boundary of the valid window. The total work across all merge steps is O(n log n).

This is the same inversion-counting trick used in LC 315 and LC 493, generalised to a range condition instead of a single comparison.

Visual Dry Run#

Let us trace nums = [-2, 5, -1], lower = -2, upper = 2.

Build the prefix array#

P = [0, -2, 3, 2]
     ^    ^   ^  ^
    P[0] P[1] P[2] P[3]

We now need pairs (a, b) with a < b and P[b] - upper <= P[a] <= P[b] - lower.

Call tree of merge_sort(P = [0, -2, 3, 2])#

merge_sort([0, -2, 3, 2])
├── merge_sort([0, -2])
│   ├── merge_sort([0])     → sorted: [0],   count: 0
│   └── merge_sort([-2])   → sorted: [-2],  count: 0
│   Merge step for [0] vs [-2]:
│     For right element -2: window = [-2 - 2, -2 - (-2)] = [-4, 0]
│       Count left elements in [-4, 0]: only 0 qualifies → count += 1
│   Merged: [-2, 0],  count from this level: 1
│
└── merge_sort([3, 2])
    ├── merge_sort([3])     → sorted: [3],   count: 0
    └── merge_sort([2])    → sorted: [2],   count: 0
    Merge step for [3] vs [2]:
      For right element 2: window = [2 - 2, 2 - (-2)] = [0, 4]
        Count left elements in [0, 4]: only 3 qualifies → count += 1
    Merged: [2, 3],  count from this level: 1
 
Merge step for [-2, 0] vs [2, 3]:
  For right element 2: window = [2 - 2, 2 - (-2)] = [0, 4]
    Scan left half [-2, 0]: lo stops at index 1 (0 >= 0), hi stops at index 2 (no more)
    Count: 2 - 1 = 1  → count += 1
  For right element 3: window = [3 - 2, 3 - (-2)] = [1, 5]
    lo pointer: 0 < 1? yes, advance. -2 < 1? yes, advance. lo now at index 2 (past end).
    hi pointer was at index 2 (past end).
    Count: 2 - 2 = 0  → count += 0
  Merge left+right normally → [-2, 0, 2, 3]
  Count from this level: 1

Tally#

Level 1 left  (merge [0] vs [-2]):   1
Level 1 right (merge [3] vs [2]):    1
Level 2       (merge halves):        1
Total:                                3  ✓

The answer matches the expected output of 3. The three valid pairs correspond to:

• P[1] - P[0] = -2 - 0 = -2 → range [0,0]
• P[3] - P[2] = 2 - 3 = -1 → range [2,2]
• P[3] - P[0] = 2 - 0 = 2 → range [0,2]

Common Mistakes#

1. Forgetting the sentinel zero in the prefix array.

The prefix array must start with P[0] = 0, not with nums[0]. Without this sentinel, subarrays that start at index 0 are never considered, because there is no earlier prefix value for them to pair with. This is a subtle off-by-one that causes you to under-count and fail on cases like nums = [0], lower = 0, upper = 0.

2. Using the wrong window formula.

The condition lower <= P[b] - P[a] <= upper rearranges to P[b] - upper <= P[a] <= P[b] - lower. A common error is to flip upper and lower: writing P[b] - lower <= P[a] <= P[b] - upper produces an empty window (since lower <= upper, so P[b] - lower <= P[b] - upper is only true when lower = upper). Always derive the rearrangement from first principles during an interview.

3. Counting before sorting vs. sorting before counting.

In the merge step, you must count valid pairs from the current sorted left and right halves before you merge them. If you merge first and then try to count, you lose the cross-half ordering information — you can no longer distinguish which values came from which half. The count step and the merge step must remain separate.

4. Integer overflow on prefix sums.

nums[i] can be as large as 2^31 - 1 in magnitude, and there can be 10^5 elements, so the prefix sum can reach 10^5 * 2^31 ≈ 2^48. In Python this is handled automatically. In JavaScript, you must use BigInt or ensure all prefix sums are within safe integer range. Failing to account for overflow produces wrong answers on edge-case inputs.

5. Moving the two pointers incorrectly.

For each right element r, the left-boundary pointer lo advances while left[lo] < r - upper, and the right-boundary pointer hi advances while left[hi] <= r - lower. A common mistake is writing strict < for both, which misses the upper boundary element, or writing <= for both, which double-counts the element at the upper boundary. The asymmetry (< for lo, <= for hi) is intentional and must be preserved.

Solutions#

Brute Force — O(n^2)#

Before jumping to merge sort, the brute force builds intuition. Compute every subarray sum directly and check if it falls in [lower, upper].

Python — Brute Force#

def countRangeSum(nums: list[int], lower: int, upper: int) -> int:
    n = len(nums)
    count = 0
 
    # Try every possible starting index i
    for i in range(n):
        running_sum = 0
 
        # Extend the subarray to every ending index j >= i
        for j in range(i, n):
            running_sum += nums[j]   # accumulate sum(i..j) incrementally
 
            # Check if this subarray sum falls within [lower, upper]
            if lower <= running_sum <= upper:
                count += 1
 
    return count

JavaScript — Brute Force#

/**
 * @param {number[]} nums
 * @param {number} lower
 * @param {number} upper
 * @return {number}
 */
var countRangeSum = function(nums, lower, upper) {
    const n = nums.length;
    let count = 0;
 
    // Try every starting index i
    for (let i = 0; i < n; i++) {
        let runningSum = 0;
 
        // Extend to every ending index j >= i
        for (let j = i; j < n; j++) {
            runningSum += nums[j];   // build sum(i..j) without recomputing
 
            // Count if the sum lands in the target window
            if (runningSum >= lower && runningSum <= upper) {
                count++;
            }
        }
    }
 
    return count;
};

The brute force works but runs in O(n^2) time, which times out for n = 10^5.

Optimal — Prefix Sum + Merge Sort, O(n log n)#

Python — Merge Sort#

def countRangeSum(nums: list[int], lower: int, upper: int) -> int:
    # Build prefix sum array with a leading sentinel 0.
    # P[k] = sum of nums[0..k-1], so sum(i,j) = P[j+1] - P[i].
    prefix = [0]
    for n in nums:
        prefix.append(prefix[-1] + n)
 
    def merge_sort(arr):
        # Base case: a single element has no pairs to count.
        if len(arr) <= 1:
            return arr, 0
 
        mid = len(arr) // 2
 
        # Recursively sort both halves and accumulate their pair counts.
        left, left_count = merge_sort(arr[:mid])
        right, right_count = merge_sort(arr[mid:])
 
        count = left_count + right_count
 
        # --- Count valid cross-half pairs ---
        # For each right element r, count left elements a where:
        #   r - upper <= a <= r - lower
        # Both left and right are sorted, so lo and hi only move forward.
        lo = hi = 0
        for r in right:
            # Advance lo until left[lo] >= r - upper (lower bound of window)
            while lo < len(left) and left[lo] < r - upper:
                lo += 1
            # Advance hi until left[hi] > r - lower (past upper bound of window)
            while hi < len(left) and left[hi] <= r - lower:
                hi += 1
            # All elements between lo and hi (exclusive) are valid for this r
            count += hi - lo
 
        # --- Standard merge of two sorted halves ---
        merged = []
        i = p = 0
        while i < len(left) and p < len(right):
            if left[i] <= right[p]:
                merged.append(left[i])
                i += 1
            else:
                merged.append(right[p])
                p += 1
        # Append any remaining elements from either half
        merged.extend(left[i:])
        merged.extend(right[p:])
 
        return merged, count
 
    # Run merge sort on the full prefix array and return the total count.
    _, total = merge_sort(prefix)
    return total

JavaScript — Merge Sort#

/**
 * @param {number[]} nums
 * @param {number} lower
 * @param {number} upper
 * @return {number}
 */
var countRangeSum = function(nums, lower, upper) {
    // Build prefix sums. prefix[k] = sum of nums[0..k-1].
    // The leading 0 acts as a sentinel for subarrays starting at index 0.
    const prefix = [0];
    for (const n of nums) {
        prefix.push(prefix[prefix.length - 1] + n);
    }
 
    /**
     * Recursively sort arr and count cross-half pairs
     * where right[j] - left[i] is in [lower, upper].
     * Returns [sortedArray, pairCount].
     */
    function mergeSort(arr) {
        // Base case: one element, zero pairs.
        if (arr.length <= 1) return [arr, 0];
 
        const mid = Math.floor(arr.length / 2);
 
        // Sort and count within each half separately.
        const [left, leftCount] = mergeSort(arr.slice(0, mid));
        const [right, rightCount] = mergeSort(arr.slice(mid));
 
        let count = leftCount + rightCount;
 
        // --- Count valid cross-half pairs ---
        // For each element r in the sorted right half, find the range
        // of elements in the sorted left half that satisfy:
        //   r - upper <= left[a] <= r - lower
        let lo = 0, hi = 0;
        for (const r of right) {
            // lo: first index where left[lo] >= r - upper
            while (lo < left.length && left[lo] < r - upper) lo++;
            // hi: first index where left[hi] > r - lower
            while (hi < left.length && left[hi] <= r - lower) hi++;
            // Elements at indices lo..hi-1 all satisfy the condition for r
            count += hi - lo;
        }
 
        // --- Standard two-pointer merge ---
        const merged = [];
        let i = 0, j = 0;
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                merged.push(left[i++]);
            } else {
                merged.push(right[j++]);
            }
        }
        // Drain whichever half still has elements
        while (i < left.length) merged.push(left[i++]);
        while (j < right.length) merged.push(right[j++]);
 
        return [merged, count];
    }
 
    // The total pair count is the second element of the result tuple.
    const [, total] = mergeSort(prefix);
    return total;
};

Complexity Analysis#

The merge sort approach has O(log n) levels of recursion, and at each level the two-pointer counting and the merge step together touch every element once, giving O(n) work per level. The total is O(n log n).

Space is O(n) for the prefix array and the temporary merge buffers. The recursion stack itself is O(log n) deep. In Python the slice-based implementation allocates O(n log n) intermediate arrays in total, but only O(n) are live at any one time.

Follow-up Questions#

Interviewers who give you this problem will frequently ask one or more of the following.

1. Can you solve it with a Binary Indexed Tree (BIT / Fenwick Tree)?

Yes. The idea: iterate through the prefix array left to right. For each P[b], query the BIT for the count of previously inserted values in [P[b] - upper, P[b] - lower], then insert P[b]. Because BIT requires integer indices, you first need to coordinate-compress all distinct prefix values and all window boundaries to a dense integer range. This is a standard competitive-programming pattern. Time: O(n log n). Space: O(n).

2. How does this relate to LC 315 — Count of Smaller Numbers After Self?

LC 315 asks for exactly the same structural thing: for each index j, count how many later-index values are smaller. The merge-sort solution to LC 315 counts cross-half pairs during the merge where right[j] < left[i] — a single-sided inequality instead of a range. The template is identical; only the counting condition changes. Solving LC 327 first makes LC 315 trivially easy.

3. How does this relate to LC 493 — Reverse Pairs?

LC 493 counts pairs (i, j) with i < j and nums[i] > 2 * nums[j]. Again the same divide-and-conquer skeleton applies. The counting step uses a single two-pointer advance (not two pointers for a range), because the condition is a one-sided comparison. The merge step in LC 493 must be kept separate from the counting step because the condition nums[i] > 2 * nums[j] does not produce a sorted merge-compatible order on its own. Recognising this family of problems — all solved by "count across halves during merge sort" — is the most valuable takeaway from studying LC 327.

4. What if nums contains duplicates or all zeros?

The algorithm handles duplicates without modification: the prefix array may contain repeated values, but the two-pointer scan on sorted halves correctly counts all qualifying indices, including multiple elements at the same value. The edge case lower = upper = 0 and nums = [0, 0, 0] produces 6 valid subarrays (n*(n+1)/2), and the merge sort count will produce exactly 6.

This Pattern Solves#

The prefix-sum + merge-sort counting pattern applies whenever you need to count pairs of indices (a, b) with a < b where the pair satisfies a condition that can be evaluated on a sorted version of a derived array:

• Inversion count — pairs where arr[a] > arr[b] with a < b. Classic divide-and-conquer.
• Count of Smaller Numbers After Self (LC 315) — single-sided cross-half comparison.
• Reverse Pairs (LC 493) — scaled single-sided comparison.
• Count of Range Sum (LC 327) — range condition on prefix differences.
• Global inversions vs. local inversions (LC 775) — difference between inversion count and adjacent-pair count.
• K-th smallest pair distance (LC 719) — binary search on the answer with a counting subroutine that uses a two-pointer scan on a sorted array.

The key structural question to ask yourself: "If I sort one of the two involved sequences, can I count the valid elements in the other with a binary search or two-pointer scan?" If yes, divide-and-conquer or a sorted data structure will give O(n log n).

Key Takeaways#

• Count of Range Sum (LC 327) transforms subarray sums into prefix-sum differences: sum(i..j) = P[j+1] - P[i]; then count pairs (l, r) with l < r where lower <= P[r] - P[l] <= upper.
• Merge sort on prefix sums counts qualifying cross-half pairs in O(n) per level using a two-pointer scan on the sorted left half.
• The two pointers advance monotonically: for each right-half index r, find the smallest window [lo, hi) in the sorted left half where P[r] - P[l] falls in [lower, upper].
• Counting and merging must stay separate passes at each merge step — interleaving them corrupts the sorted order that the count step depends on.
• O(n log n) time, O(n) space; this is the same skeleton as LC 315 (Count Smaller After Self) and LC 493 (Reverse Pairs).
• A sorted multiset (SortedList in Python, TreeMap in Java) is an alternative O(n log n) approach that avoids recursion overhead.
• This problem is a masterclass in problem transformation: convert the domain (subarray sums → prefix differences → sorted pairs) so that a fast counting algorithm becomes applicable.