Given an integer array nums and two integers lower and upper, return the number of range sums that lie in [lower, upper] inclusive.
Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j inclusive, where i <= j.
Example 1:
Input: nums = [-2,5,-1], lower = -2, upper = 2 Output: 3 Explanation: The three ranges are: [0,0], [2,2], and [0,2] and their respective sums are: -2, -1, 2.
Example 2:
Input: nums = [0], lower = 0, upper = 0 Output: 1
Constraints:
1 <= nums.length <= 105-231 <= nums[i] <= 231 - 1-105 <= lower <= upper <= 105Problem Overview: Given an integer array nums and two integers lower and upper, count the number of subarrays whose sum lies within the inclusive range [lower, upper]. The challenge is efficiently evaluating all possible subarray sums without explicitly enumerating every pair.
The key observation is that subarray sums can be rewritten using prefix sums. If prefix[i] represents the sum of the first i elements, then the sum of subarray (i, j] equals prefix[j] - prefix[i]. The problem becomes: for every j, count how many earlier prefix values satisfy lower ≤ prefix[j] - prefix[i] ≤ upper.
Approach 1: Naive Iteration with Prefix Sums (Time: O(n²), Space: O(n))
Start by building a prefix sum array so each subarray sum can be computed in constant time. Iterate over every possible pair of indices (i, j) where i < j, compute the subarray sum using prefix[j] - prefix[i], and check if it falls within the target range. This avoids recomputing sums repeatedly but still examines all O(n²) subarrays.
This method is easy to implement and useful for validating correctness during development. However, it becomes too slow when the input size approaches the typical constraints (up to tens of thousands of elements). The approach mainly demonstrates the relationship between subarray sums and prefix differences in an array.
Approach 2: Merge Sort with Prefix Sums (Time: O(n log n), Space: O(n))
The optimized solution uses a modified divide and conquer strategy similar to counting inversions. Compute the prefix sum array first. While performing a merge sort on this array, count valid pairs across the left and right halves.
For each prefix value in the left half, maintain two pointers in the right half that represent the valid window where lower ≤ rightPrefix - leftPrefix ≤ upper. Because both halves are sorted during the merge step, these pointers only move forward, allowing the algorithm to count valid ranges in linear time per merge level. After counting, perform the normal merge to keep the prefix array sorted.
This reduces the overall complexity to O(n log n), making it scalable for large inputs. The algorithm relies on sorting properties and efficient window counting instead of explicitly enumerating subarrays.
Recommended for interviews: Interviewers typically expect the merge-sort-based prefix sum approach. The brute force solution shows you understand the prefix sum transformation, but the O(n log n) divide-and-conquer strategy demonstrates stronger algorithmic thinking and familiarity with advanced counting techniques.
This approach involves using two nested loops to calculate the range sum for each subarray and checks if it lies between the given range [lower, upper]. The approach is straightforward but results in O(n^2) time complexity, making it inefficient for large input sizes.
The C solution iterates through all possible subarrays, calculating the sum for each and checking if it fits within [lower, upper]. It uses two nested loops where the outer loop starts at each element and the inner loop extends the subarray to the right, ensuring the sum of elements is calculated incrementally.
Time Complexity: O(n^2), where n is the number of elements in the array.
Space Complexity: O(1), as no additional space is needed.
This approach utilizes merge sort combined with prefix sums to efficiently calculate and count the number of range sums within the given boundaries. The key insight is that any valid range must be a difference between two prefix sums. By maintaining and sorting prefix sums, the problem is reduced to counting the number of such prefix sums differences that fall within the range, which can be done in logarithmic time using the divide and conquer method of merge sort.
The C solution employs a recursive divide and conquer technique through the merge sort process on the prefix sums. It ensures that the total range sum count is generated by maintaining a sorted prefix sum array, where each pair of sums[i], sums[j] (j > i) represents a potential valid range.
Time Complexity: O(n log n), where n is the length of the array.
Space Complexity: O(n), for the prefix sum array and auxiliary space used during merging.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Naive Iteration | Time Complexity: O(n^2), where n is the number of elements in the array. |
| Approach 2: Merge Sort with Prefix Sums | Time Complexity: O(n log n), where n is the length of the array. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Iteration with Prefix Sums | O(n²) | O(n) | Good for understanding the prefix sum transformation or verifying small inputs |
| Merge Sort with Prefix Sums | O(n log n) | O(n) | Best general solution for large arrays and typical interview expectations |
LeetCode 327. Count of Range Sum Explanation and Solution • happygirlzt • 19,095 views views
Watch 9 more video solutions →Practice Count of Range Sum with our built-in code editor and test cases.
Practice on FleetCode