Watch 10 video solutions for Count of Range Sum, a hard level problem involving Array, Binary Search, Divide and Conquer. This walkthrough by happygirlzt has 19,095 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |