LeetCode Problem 327

Difficulty: 🔴 Hard
Topics: Array, Binary Search, Divide and Conquer, Binary Indexed Tree, Segment Tree, Merge Sort, Ordered Set

Solution

LeetCode 327 - Count of Range Sum

Problem Understanding

This problem asks us to count how many subarrays have sums that fall within a given inclusive range [lower, upper].

A range sum S(i, j) represents the sum of all elements from index i through index j in the array. For every possible pair (i, j) where i <= j, we compute the subarray sum and check whether it lies between lower and upper.

The input consists of:

• An integer array nums
• Two integers lower and upper

The expected output is the total number of valid subarrays whose sums satisfy:

$$lower \leq S(i, j) \leq upper$$

The constraints are extremely important:

• nums.length can be as large as 10^5
• Array values can be very large positive or negative integers
• The answer fits within a 32-bit integer

These constraints immediately tell us that an O(n^2) solution will not be fast enough. With 10^5 elements, there are roughly 10^{10} subarrays, which is far beyond practical runtime limits.

The presence of negative numbers is also significant. If all numbers were non-negative, we could potentially use a sliding window technique. However, because negative values can decrease the running sum unpredictably, sliding window methods do not work here.

Several edge cases are especially important:

• Arrays containing negative values
• Arrays containing zeros
• Very large positive and negative integers
• Cases where every subarray is valid
• Cases where no subarray is valid
• Single-element arrays
• Duplicate prefix sums

A correct solution must efficiently count valid subarray sums without explicitly enumerating every subarray.

Approaches

Brute Force Approach

The most direct solution is to examine every possible subarray.

We can generate all (i, j) pairs, compute the sum of nums[i:j+1], and check whether the sum lies within [lower, upper].

A naive implementation would recompute each subarray sum from scratch, resulting in O(n^3) complexity. Using prefix sums improves this to O(n^2) because each subarray sum can then be computed in constant time.

The idea is:

• Build a prefix sum array
• For every pair (i, j), compute:

$$S(i, j) = prefix[j+1] - prefix[i]$$

• Count how many satisfy the range condition

This approach is correct because it checks every possible subarray exactly once.

However, it is still too slow for n = 10^5.

Optimal Approach, Prefix Sums + Modified Merge Sort

The key insight is to transform the problem into counting pairs of prefix sums.

Define:

$$prefix[k] = nums[0] + nums[1] + \dots + nums[k-1]$$

Then any subarray sum becomes:

$$S(i, j) = prefix[j+1] - prefix[i]$$

We need to count pairs (i, j) such that:

$$lower \leq prefix[j] - prefix[i] \leq upper$$

Rearranging:

$$prefix[j] - upper \leq prefix[i] \leq prefix[j] - lower$$

So for each prefix sum, we need to count how many earlier prefix sums fall inside a particular range.

This becomes a counting problem over sorted prefix sums.

A modified merge sort works well because:

• Merge sort naturally divides the array into sorted halves
• During merging, we can efficiently count valid cross-half pairs using two pointers
• Each level of recursion processes all elements in linear time
• Total complexity becomes O(n log n)

This is efficient enough for the constraints.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Uses prefix sums but still checks all subarrays
Optimal	O(n log n)	O(n)	Uses prefix sums with modified merge sort counting

Algorithm Walkthrough

1. First, build a prefix sum array.

We create an array prefix where:

$$prefix[i]$$

stores the sum of the first i elements.

We initialize with 0 because a subarray can start at index 0. 2. Convert the problem into counting prefix sum pairs.

For every pair (i, j) where i < j, the subarray sum is:

$$prefix[j] - prefix[i]$$

We need this value to lie between lower and upper. 3. Apply merge sort to the prefix sum array.

Merge sort recursively divides the array into two sorted halves.

While combining the halves, we count valid pairs where:

• The left prefix sum comes from the left half
• The right prefix sum comes from the right half

4. For each left-side prefix sum, find the valid window in the right half.

Suppose we are examining a left prefix sum:

$$prefix[i]$$

We need all right-side prefix sums satisfying:

$$lower \leq prefix[j] - prefix[i] \leq upper$$

Rearranging:

$$prefix[i] + lower \leq prefix[j] \leq prefix[i] + upper$$ 5. Use two pointers to track the valid range.

Since the right half is already sorted:

• Pointer start moves until values become large enough
• Pointer end moves until values exceed the upper bound

Then:

$$end - start$$

gives the number of valid right-side prefix sums for the current left prefix sum. 6. Continue for all left-side prefix sums.

Because the halves are sorted, the pointers only move forward. This keeps the counting step linear. 7. Merge the two sorted halves.

After counting, we perform the normal merge step from merge sort to maintain sorted order for higher recursive levels. 8. Return the total count accumulated across all recursive calls.

Why it works

The correctness comes from the prefix sum transformation.

Every subarray sum can be represented as the difference between two prefix sums. The modified merge sort guarantees that every valid pair is counted exactly once when the two prefix sums belong to different halves during recursion.

Because each recursive level maintains sorted order, two-pointer scanning correctly counts all valid pairs in linear time.

Python Solution

from typing import List

class Solution:
    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
        prefix_sums = [0]

        for num in nums:
            prefix_sums.append(prefix_sums[-1] + num)

        def merge_sort(left: int, right: int) -> int:
            if right - left <= 1:
                return 0

            mid = (left + right) // 2

            count = merge_sort(left, mid)
            count += merge_sort(mid, right)

            start = mid
            end = mid

            for i in range(left, mid):
                while start < right and prefix_sums[start] - prefix_sums[i] < lower:
                    start += 1

                while end < right and prefix_sums[end] - prefix_sums[i] <= upper:
                    end += 1

                count += end - start

            merged = []
            p1 = left
            p2 = mid

            while p1 < mid and p2 < right:
                if prefix_sums[p1] <= prefix_sums[p2]:
                    merged.append(prefix_sums[p1])
                    p1 += 1
                else:
                    merged.append(prefix_sums[p2])
                    p2 += 1

            while p1 < mid:
                merged.append(prefix_sums[p1])
                p1 += 1

            while p2 < right:
                merged.append(prefix_sums[p2])
                p2 += 1

            prefix_sums[left:right] = merged

            return count

        return merge_sort(0, len(prefix_sums))

The implementation begins by constructing the prefix sum array. The initial 0 is essential because it allows subarrays starting from index 0 to be represented naturally.

The recursive merge_sort function operates on a range of the prefix sum array. If the range contains fewer than two elements, there are no pairs to count.

The recursion divides the array into two halves. Each half is recursively processed so that all valid pairs inside those halves are counted first.

The important logic occurs during the merge phase. For every prefix sum in the left half, two pointers determine the valid interval in the right half where the difference lies within [lower, upper].

Because the right half is sorted, the pointers only move forward. This avoids repeated scanning and keeps the runtime linear for each merge level.

Finally, the standard merge step restores sorted order so higher recursive calls can continue using efficient two-pointer counting.

Go Solution

func countRangeSum(nums []int, lower int, upper int) int {
	prefixSums := make([]int64, len(nums)+1)

	for i, num := range nums {
		prefixSums[i+1] = prefixSums[i] + int64(num)
	}

	var mergeSort func(left, right int) int

	mergeSort = func(left, right int) int {
		if right-left <= 1 {
			return 0
		}

		mid := (left + right) / 2

		count := mergeSort(left, mid)
		count += mergeSort(mid, right)

		start := mid
		end := mid

		for i := left; i < mid; i++ {
			for start < right &&
				prefixSums[start]-prefixSums[i] < int64(lower) {
				start++
			}

			for end < right &&
				prefixSums[end]-prefixSums[i] <= int64(upper) {
				end++
			}

			count += end - start
		}

		merged := make([]int64, 0, right-left)

		p1 := left
		p2 := mid

		for p1 < mid && p2 < right {
			if prefixSums[p1] <= prefixSums[p2] {
				merged = append(merged, prefixSums[p1])
				p1++
			} else {
				merged = append(merged, prefixSums[p2])
				p2++
			}
		}

		for p1 < mid {
			merged = append(merged, prefixSums[p1])
			p1++
		}

		for p2 < right {
			merged = append(merged, prefixSums[p2])
			p2++
		}

		copy(prefixSums[left:right], merged)

		return count
	}

	return mergeSort(0, len(prefixSums))
}

The Go implementation closely mirrors the Python solution, but there are several language-specific considerations.

The most important difference is the use of int64 for prefix sums. Since prefix sums can grow beyond the range of a 32-bit integer, using int64 avoids overflow issues.

Go slices are used instead of Python lists. During merging, a temporary slice is allocated and later copied back into the original prefix sum slice.

Unlike Python, Go does not support nested list assignment directly, so the copy function is used to overwrite the relevant range.

Worked Examples

Example 1

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

Step 1: Build Prefix Sums

Index	Prefix Sum
0	0
1	-2
2	3
3	2

So:

prefix = [0, -2, 3, 2]

Step 2: Count Valid Differences

We examine all pairs (i, j) where i < j.

i	j	prefix[j] - prefix[i]	Valid?
0	1	-2	Yes
0	2	3	No
0	3	2	Yes
1	2	5	No
1	3	4	No
2	3	-1	Yes

Total valid subarrays:

3

Merge Sort Counting Process

Initial prefix array:

[0, -2, 3, 2]

After recursive sorting:

[-2, 0, 2, 3]

During merge phases, valid ranges are counted using two pointers instead of brute force pair checking.

Example 2

nums = [0]
lower = 0
upper = 0

Prefix Sums

Index	Prefix Sum
0	0
1	0

Possible pair:

i	j	Difference	Valid
0	1	0	Yes

Answer:

1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Merge sort has log n levels, each level processes all elements
Space	O(n)	Extra space is used for merging and recursion

The algorithm achieves O(n log n) complexity because each merge sort level processes the entire prefix sum array in linear time. The two-pointer counting step is also linear since pointers never move backward.

The space complexity is O(n) due to the temporary merged arrays and recursion stack.

Test Cases

sol = Solution()

# Provided examples
assert sol.countRangeSum([-2, 5, -1], -2, 2) == 3  # standard example
assert sol.countRangeSum([0], 0, 0) == 1  # single zero element

# Single element cases
assert sol.countRangeSum([5], 5, 5) == 1  # exact match
assert sol.countRangeSum([5], 1, 4) == 0  # no valid range
assert sol.countRangeSum([-5], -5, -5) == 1  # negative single value

# All zeros
assert sol.countRangeSum([0, 0, 0], 0, 0) == 6  # every subarray valid

# Mixed positive and negative
assert sol.countRangeSum([1, -1, 1], 0, 1) == 5  # overlapping valid ranges

# No valid subarrays
assert sol.countRangeSum([10, 20, 30], -5, 5) == 0  # none fit

# Large negative values
assert sol.countRangeSum([-1, -1, -1], -2, -1) == 5  # multiple negatives

# Prefix sum duplicates
assert sol.countRangeSum([1, -1, 1, -1], 0, 0) == 4  # repeated prefix sums

# Entire array valid
assert sol.countRangeSum([2, 2, 2], 6, 6) == 1  # full array only

# Stress style small case
assert sol.countRangeSum([1, 2, 3, 4], 3, 6) == 5  # multiple valid ranges

Test Summary

Test	Why
[-2,5,-1]	Standard mixed positive and negative case
[0]	Smallest possible array
[5] exact match	Single valid element
[5] invalid range	Single invalid element
[-5]	Negative single value
[0,0,0]	Many duplicate prefix sums
[1,-1,1]	Alternating sums
[10,20,30]	No valid subarrays
[-1,-1,-1]	Multiple negative ranges
[1,-1,1,-1]	Duplicate prefix sum behavior
[2,2,2]	Entire array valid
[1,2,3,4]	Multiple overlapping valid intervals

Edge Cases

Single Element Arrays

A single-element array is the smallest valid input size. Bugs often occur when implementations assume there are at least two elements or fail to initialize the prefix sum array correctly.

This implementation handles the case naturally because the prefix sum array always begins with an initial 0, allowing single-element subarrays to be represented as differences between two prefix sums.

Arrays With Many Duplicate Prefix Sums

Arrays such as [0, 0, 0] generate repeated prefix sums:

[0, 0, 0, 0]

This can cause counting errors if the merge logic mishandles equal values or pointer movement.

The implementation correctly handles duplicates because the merge step preserves sorted order and the counting logic uses inclusive bounds carefully:

• < lower
• <= upper

This guarantees exact counting without missing or double-counting equal prefix sums.

Large Positive and Negative Numbers

The constraints allow values near the 32-bit integer limits. Prefix sums can exceed standard integer ranges if accumulated repeatedly.

The Python solution handles this automatically because Python integers have arbitrary precision.

The Go solution explicitly uses int64 for prefix sums to prevent overflow during accumulation and subtraction operations.