Count of Range Sum — Merge Sort on Prefix Sums [LC 327]

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 S(i, j) is defined as the sum of nums[i] through nums[j-1] (0-indexed, exclusive right).

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

Example 1:

Input:  nums = [-2, 5, -1], lower = -2, upper = 2
Output: 3
Explanation:
  S(0,1) = -2         (in range)
  S(0,2) = 3          (out of range)
  S(0,3) = 2          (in range)
  S(1,2) = 5          (out of range)
  S(1,3) = 4          (out of range)
  S(2,3) = -1         (in range)
  Three sums lie in [-2, 2].

Example 2:

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

Example 3:

Input:  nums = [1, -1], lower = 0, upper = 0
Output: 1
Explanation: S(0,2) = 0, which is in [0, 0].

Why This Problem Matters#

LC 327 is a classic hard problem that exposes the merge-sort counting pattern — the same idea behind Count of Smaller Numbers After Self (LC 315) and Reverse Pairs (LC 493). It is asked at Google and Jane Street because it requires combining two distinct techniques: prefix sums and divide-and-conquer.

The problem matters because it teaches you that counting constraints on ranges of a sorted sequence can be embedded into the merge step of merge sort at no additional asymptotic cost. Once you internalise this, a whole category of hard array problems becomes tractable.

The brute-force O(n²) solution — compute all prefix sums and check every pair — is immediately obvious. The challenge is getting to O(n log n). This problem is a perfect vehicle for that lesson.

The Core Insight#

Step 1 — Prefix sums. Define prefix[0] = 0, prefix[i] = nums[0] + ... + nums[i-1]. Then the range sum S(i, j) = prefix[j] - prefix[i]. We need to count pairs (i, j) with i < j such that lower <= prefix[j] - prefix[i] <= upper.

Step 2 — Merge sort counting. During a standard merge sort on the prefix array, when we merge a left half L and right half R (both already sorted), we count valid pairs (L[i], R[j]) such that lower <= R[j] - L[i] <= upper. Because R is sorted, for each fixed L[i], valid R[j] values form a contiguous window [j_lo, j_hi). Two pointers j and k advance monotonically across all L[i], giving O(n) count per merge level.

The total work across all O(log n) merge levels is O(n log n).

Key invariant: The left and right halves are already sorted before merging, so the two-pointer window technique is valid.

Visual Dry Run#

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

Prefix array: [0, -2, 3, 2]

Merge sort divides into:

[0, -2, 3, 2]
  [0, -2]  [3, 2]
[0] [-2]  [3] [2]

Merge [0] and [-2]:

• Sorted L = [0], sorted R = [-2]
• For L[0]=0: need R[j] in [0+lower, 0+upper] = [-2, 2]. R[j]=-2 qualifies. Count = 1.
• Merged: [-2, 0]

Merge [3] and [2]:

• L = [3], R = [2]
• For L[0]=3: need R[j] in [3-2, 3+2] = [1, 5]. R[j]=2 qualifies. Count = 1.
• Wait — we want R[j] - L[i] in [-2,2], i.e. R[j] in [L[i]+lower, L[i]+upper] = [3-2, 3+2] = [1,5]. R[j]=2 is in [1,5]. Count = 1.
• Merged: [2, 3]

Merge [-2, 0] and [2, 3]:

• L = [-2, 0], R = [2, 3]
• For L[0]=-2: need R[j] in [-2-2, -2+2] = [-4, 0]. No R values in range. Count += 0.
• For L[1]=0: need R[j] in [0-2, 0+2] = [-2, 2]. R[0]=2 qualifies. Count += 1.
• Merged: [-2, 0, 2, 3]

Total pairs found: 1 + 1 + 1 = 3. Matches expected output.

Common Mistakes#

1. Using int instead of long for prefix sums. Each nums[i] can be up to 2^31 - 1, and summing 10^5 of them overflows a 32-bit integer. Always use 64-bit integers for prefix sums in this problem.

2. Checking R[j] - L[i] bounds wrong. The condition is lower <= R[j] - L[i] <= upper, which means L[i] + lower <= R[j] <= L[i] + upper. Getting the rearrangement wrong produces an off-by-one in the window.

3. Forgetting that the merge step must actually sort the array. The counting is embedded in the merge, but you must still complete the merge and write sorted values back. Skipping the sort breaks future merge levels.

4. Using arr[:] = sorted(arr) inside the merge (O(n log n) per call). This degrades the overall complexity to O(n log²n). Use a proper in-place merge with a temporary array for O(n) per level.

5. Not including the initial prefix[0] = 0. Without it, you miss all subarrays that start at index 0. The prefix array must have n+1 elements.

6. Starting j and k from 0 for each L[i]. The two pointers must carry over between iterations of L[i] to maintain O(n) total work per merge level.

Solutions#

Python#

def countRangeSum(nums: list[int], lower: int, upper: int) -> int:
    # Build prefix sum array (length n+1, starts with 0)
    prefix = [0] * (len(nums) + 1)
    for i, x in enumerate(nums):
        prefix[i + 1] = prefix[i] + x          # prefix[i+1] = sum of nums[0..i]
 
    def merge_count(arr: list[int]) -> int:
        """Sort arr in-place and return count of valid pairs."""
        n = len(arr)
        if n <= 1:
            return 0                             # base case: single element, no pairs
 
        mid = n // 2
        count = merge_count(arr[:mid])          # count in left half (also sorts it)
        count += merge_count(arr[mid:])         # count in right half (also sorts it)
 
        left = arr[:mid]                        # sorted left half
        right = arr[mid:]                       # sorted right half
 
        # Two pointers: find valid right[j] for each left[i]
        # We need lower <= right[j] - left[i] <= upper
        # i.e. left[i] + lower <= right[j] <= left[i] + upper
        j = 0                                   # pointer to first right[j] >= left[i]+lower
        k = 0                                   # pointer to first right[j] > left[i]+upper
 
        for li in left:
            # Advance j: right[j] < li + lower
            while j < len(right) and right[j] < li + lower:
                j += 1
            # Advance k: right[k] <= li + upper
            while k < len(right) and right[k] <= li + upper:
                k += 1
            count += k - j                      # all indices in [j, k) are valid
 
        # Merge left and right back into arr (standard merge)
        p, q, idx = 0, 0, 0
        temp = []
        while p < len(left) and q < len(right):
            if left[p] <= right[q]:
                temp.append(left[p]); p += 1
            else:
                temp.append(right[q]); q += 1
        temp.extend(left[p:])
        temp.extend(right[q:])
        arr[:] = temp                           # write sorted result back
 
        return count
 
    return merge_count(prefix)

JavaScript#

function countRangeSum(nums, lower, upper) {
    const n = nums.length;
 
    // Build prefix sum array using BigInt to avoid overflow
    const prefix = new Array(n + 1).fill(0n);
    for (let i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + BigInt(nums[i]);  // 64-bit arithmetic
    }
 
    const lowerBig = BigInt(lower);
    const upperBig = BigInt(upper);
 
    function mergeCount(arr, lo, hi) {
        // Sort arr[lo..hi) and return count of valid cross-pairs
        if (hi - lo <= 1) return 0;            // base case
 
        const mid = Math.floor((lo + hi) / 2);
        let count = mergeCount(arr, lo, mid);   // sort and count left half
        count += mergeCount(arr, mid, hi);      // sort and count right half
 
        // Two-pointer count: pairs (arr[i], arr[j]) with i in [lo,mid), j in [mid,hi)
        let j = mid;                            // first j where arr[j] - arr[i] >= lower
        let k = mid;                            // first k where arr[k] - arr[i] > upper
 
        for (let i = lo; i < mid; i++) {
            // Advance j: arr[j] - arr[i] < lower  =>  arr[j] < arr[i] + lower
            while (j < hi && arr[j] - arr[i] < lowerBig) j++;
            // Advance k: arr[k] - arr[i] <= upper  =>  arr[k] <= arr[i] + upper
            while (k < hi && arr[k] - arr[i] <= upperBig) k++;
            count += k - j;                     // all indices [j, k) are valid
        }
 
        // Standard merge into temporary array
        const temp = [];
        let p = lo, q = mid;
        while (p < mid && q < hi) {
            if (arr[p] <= arr[q]) temp.push(arr[p++]);
            else temp.push(arr[q++]);
        }
        while (p < mid) temp.push(arr[p++]);
        while (q < hi) temp.push(arr[q++]);
 
        // Write back sorted values
        for (let i = lo; i < hi; i++) arr[i] = temp[i - lo];
 
        return count;
    }
 
    return mergeCount(prefix, 0, prefix.length); // merge sort on prefix array
}

Complexity Analysis#

The merge sort solution dominates. Each of the O(log n) merge levels performs O(n) work across all merges at that level, giving O(n log n) total. The prefix array adds O(n) space.

Follow-up Questions#

1. LC 315 — Count of Smaller Numbers After Self. Same merge-sort counting pattern but for inversions. Can you adapt the merge step?
2. LC 493 — Reverse Pairs. Count pairs where nums[i] > 2 * nums[j] with i < j. The same two-pointer window trick applies inside the merge.
3. What if lower == upper? The problem reduces to counting subarrays with an exact sum. The merge approach still works, but a hash map gives O(n).
4. Can you solve this with a Binary Indexed Tree? Yes — coordinate-compress the prefix sums and use a BIT to count elements in a range at each step. O(n log n) time, similar space.

This Pattern Solves#

• LC 327 — Count of Range Sum (this problem)
• LC 315 — Count of Smaller Numbers After Self
• LC 493 — Reverse Pairs
• Any "count pairs satisfying a range constraint" problem where divide-and-conquer on a sorted structure enables two-pointer counting

Key Takeaway#

The merge-sort counting pattern works whenever you need to count pairs across the left and right halves of a divide-and-conquer split, and when the sorted property of each half lets you use two pointers to find valid pairs in O(n) per level. For Count of Range Sum, the key chain is: prefix sums convert subarray sums into pair differences, and merge sort makes those differences queryable in sorted order. Use long / BigInt for prefix sums — integer overflow is the most common silent failure in this problem.

Key Takeaways#

• LC 327 is a hard problem asked by Google and Jane Street; it requires combining prefix sums with merge-sort counting — two advanced techniques in one solution.
• Convert the problem: S(i,j) = prefix[j] - prefix[i]; count pairs where lower <= prefix[j] - prefix[i] <= upper with i < j.
• Embed counting into the merge step: when merging sorted halves L and R, use two monotone pointers to count valid (L[i], R[j]) pairs in O(n) per merge level.
• The two pointers j and k carry over between iterations of L[i] — resetting them to 0 each time degrades to O(n^2).
• Always use 64-bit integers (long in Java/C++, BigInt in JavaScript) for prefix sums — 32-bit overflow is the most common silent failure.
• The merge step must actually sort the array; the counting is embedded in the merge but the sort must complete for future levels to work correctly.
• This merge-sort counting pattern also solves LC 315 (Count of Smaller Numbers After Self) and LC 493 (Reverse Pairs) — the same two-pointer-in-merge-step technique.