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 
    # WRONG:
prefix = [0] * n + 1, 0; # ❌ May overflow
  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