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.

Thinking Process

  1. Prefix Sum Transformation: Convert subarray sum problem to prefix sum difference problem
    • Divide & Conquer: Sort prefix sums, count pairs using two pointers
    • Segment Tree: Maintain count of prefix sums, query range for each new prefix
  • Clarify if the array is sorted, has negatives, or allows duplicates.
  • Prefix sums answer range queries; hash maps answer pair/count queries.
  • In-place tricks use swap/write index instead of extra arrays.
Array + hash map 2 7 11 map hash map for O(1) lookups

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Prefix sum O(n) O(n) Range queries, subarray sum
Sort + scan O(n log n) O(1) Intervals, meeting rooms
Kadane’s algorithm O(n) O(1) Maximum subarray
Hash map counting (this problem) O(n) O(n) Frequency, two-sum variants

Examples

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 <= 10^5
  • -2^31 <= nums[i] <= 2^31 - 1
  • -10^5 <= lower <= upper <= 10^5

Common Mistakes

  1. Single element: nums = [0], lower = 0, upper = 0 → return 1
  2. All negative: nums = [-2,-1], lower = -3, upper = -1 → count valid ranges
  3. Large numbers: Use long long to prevent overflow
  4. Empty ranges: Handle cases where no valid ranges exist

  5. Overflow prevention: Prefix sums can exceed int range

  6. Integer overflow: Not using long long for prefix sums 
    class Solution {
     public int countRangeSum(int[] nums, int lower, int upper) {
     int n = nums.length;
     long[]prefix(n + 1, 0);

     // prefix sum with 0 included
     for (int i = 0; i < n; i++)
         prefix[i + 1] = prefix[i] + nums[i];

     long[]temp(n + 1);
     return divide = new return(prefix, 0, n, lower, upper, temp);
 }
     public int divide(long[] prefix, int left, int right,
            int lower, int upper, long[] temp) {
     if (left >= right) return 0;

     int mid = (left + right) / 2;
     int count = 0;

     count += divide(prefix, left, mid, lower, upper, temp);
     count += divide(prefix, mid + 1, right, lower, upper, temp);

     count += countCross(prefix, left, mid, right, lower, upper);
     merge(prefix, left, mid, right, temp);

     return count;
 }
     public int countCross(long[] prefix, int left, int mid, int right,
                int lower, int upper) {
     int count = 0;
     int wl = left, wr = left;

     for (int i = mid + 1; i <= right; i++) {
         long low = prefix[i] - upper;
         long high = prefix[i] - lower;

         while (wl <= mid && prefix[wl] < low) wl++;
         while (wr <= mid && prefix[wr] <= high) wr++;

         count += wr - wl;
     }
     return count;
 }

 public void merge(long[] prefix, int left, int mid, int right,
            long[] temp) {
     int i = left, j = mid + 1, k = left;

     while (i <= mid && j <= right)
         temp[k++] = (prefix[i] <= prefix[j]) ? prefix[i++] : prefix[j++];

     while (i <= mid) temp[k++] = prefix[i++];
     while (j <= right) temp[k++] = prefix[j++];

     for (int i = left; i <= right; i++)
         prefix[i] = temp[i];
 }
}
  7. Off-by-one errors: Incorrect prefix sum indexing
  8. Missing prefix[0]: Forgetting to include empty prefix (sum = 0)
  9. Wrong range: Confusing prefix[j] - upper and prefix[j] - lower
  10. Memory leaks: Not managing segment tree nodes properly (though solution doesn’t delete)

Key Takeaways

  1. Prefix Sum Transformation: Convert subarray sum problem to prefix sum difference problem
  2. Range Condition: lower <= prefix[j] - prefix[i] <= upper becomes prefix[j] - upper <= prefix[i] <= prefix[j] - lower
  3. Two Approaches:
    • Divide & Conquer: Sort prefix sums, count pairs using two pointers
    • Segment Tree: Maintain count of prefix sums, query range for each new prefix
  4. Dynamic Node Creation: Reduces memory for sparse segment trees

References

Template Reference