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 <= 105The key idea for Count of Range Sum is to transform the problem using prefix sums. Instead of checking every subarray directly, compute a prefix array where prefix[i] represents the sum of elements up to index i. The problem then becomes counting pairs (i, j) such that the difference prefix[j] - prefix[i] lies within the range [lower, upper].
A naive comparison of all pairs results in O(n²) time, which is too slow for large inputs. An efficient strategy uses divide and conquer with a modified merge sort. While merging two sorted halves of prefix sums, we count how many values in the right half satisfy the valid range for each value in the left half. Because both halves remain sorted, binary pointers can efficiently track valid ranges.
Alternative solutions use advanced data structures like a Binary Indexed Tree, Segment Tree, or an Ordered Set to dynamically count prefix sums within the desired interval. These approaches typically achieve O(n log n) time with additional memory for indexing or coordinate compression.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Brute Force with Prefix Sums | O(n^2) | O(n) |
| Divide and Conquer (Merge Sort Counting) | O(n log n) | O(n) |
| Binary Indexed Tree / Segment Tree | O(n log n) | O(n) |
Ashish Pratap Singh
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem is considered an advanced interview question because it combines prefix sums with divide-and-conquer or tree-based techniques. Variants of this pattern frequently appear in FAANG and other top tech company interviews.
The most efficient approach uses prefix sums combined with a modified merge sort. During the merge process, it counts valid prefix sum differences that fall within the given range. This reduces the complexity from O(n^2) to O(n log n).
Prefix sums convert the subarray sum problem into a difference between two prefix values. This transformation allows efficient counting of valid ranges using sorting, binary search, or tree-based structures.
Besides divide and conquer, data structures like Binary Indexed Trees, Segment Trees, or ordered sets can be used. These structures help efficiently count how many prefix sums fall within a specific range while iterating through the array.