How to Solve Count of Range Sum

This problem requires counting all subarrays whose sums fall within a given inclusive range. Efficient solutions leverage prefix sums combined with merge sort or segment tree approaches to handle large arrays. Understanding binary search over the valid sum space and handling overlapping ranges carefully ensures correctness without exceeding time constraints.

Problem Statement

Given an integer array nums and two integers lower and upper, determine the total number of subarrays whose sums lie between lower and upper, inclusive. A subarray is defined as a contiguous segment of nums, and sums can be negative or positive.

Formally, for indices i and j with 0 <= i <= j < nums.length, compute the sum S(i, j) = nums[i] + nums[i+1] + ... + nums[j], and count how many such sums satisfy lower <= S(i, j) <= upper. For example, nums = [-2,5,-1], lower = -2, upper = 2 produces 3 valid ranges: [0,0], [2,2], and [0,2].

Examples

Example 1

Input: nums = [-2,5,-1], lower = -2, upper = 2

Output: 3

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

Example details omitted.

Constraints

• 1 <= nums.length <= 105
• -231 <= nums[i] <= 231 - 1
• -105 <= lower <= upper <= 105
• The answer is guaranteed to fit in a 32-bit integer.

Solution Approach

Prefix Sum with Merge Sort

Compute prefix sums of nums and recursively divide the array. During merge steps, count valid sums where the difference between two prefix sums falls within [lower, upper]. This approach reduces time complexity compared to naive O(n^2) enumeration and handles overlapping ranges efficiently.

Segment Tree or Binary Indexed Tree

Map prefix sums into a sorted structure, then query ranges efficiently using a segment tree or BIT. For each new prefix sum, count how many previous sums satisfy the range condition. This approach works well when dynamic updates or multiple queries are needed.

Binary Search over Valid Sum Space

Sort all prefix sums and for each prefix sum, use binary search to find how many previous sums lie in [currentSum - upper, currentSum - lower]. This directly applies the 'binary search over the valid answer space' pattern and ensures logarithmic counting per prefix sum.

Complexity Analysis

Naive enumeration is O(n^2). Merge sort-based prefix sum counting achieves O(n log n). Segment tree or BIT approaches also achieve O(n log n) with extra space for the data structure. Space is O(n) for prefix sums, and extra O(n) for merge operations or tree structures.

What Interviewers Usually Probe

• Ask about handling negative numbers in subarray sums.
• Probe understanding of prefix sums and why merge sort helps avoid double counting.
• Expect recognition of binary search over cumulative sums as the core optimization.

Common Pitfalls or Variants

Common pitfalls

• Attempting brute-force O(n^2) sum enumeration on large arrays causes timeouts.
• Neglecting proper handling of overlapping ranges during merge can undercount valid sums.
• Failing to correctly compute prefix sum differences when applying binary search leads to off-by-one errors.

Follow-up variants

• Count of Range Sum where multiple queries on different ranges are performed, requiring dynamic updates.
• Counting subarrays with product in a range instead of sum, which changes the aggregation technique.
• Counting ranges with additional constraints, like length limits or modulo conditions.

How GhostInterview Helps

• Automatically identifies the divide-and-conquer pattern and guides prefix sum computation for accurate range counting.
• Highlights failure points in overlapping range handling and off-by-one errors during binary search.
• Provides step-by-step merge sort and segment tree strategies to achieve O(n log n) efficiency in interviews.

Topic Pages

• Array
• Binary Search
• Divide and Conquer
• Binary Indexed Tree
• Segment Tree
• Merge Sort
• Ordered Set

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What is the main pattern used in Count of Range Sum?

The key pattern is 'binary search over the valid answer space', combined with prefix sums and merge sort to count subarrays efficiently.

Can this problem be solved without merge sort?

Yes, segment trees or binary indexed trees can be used to query prefix sum ranges dynamically, still achieving O(n log n) complexity.

Why is prefix sum necessary here?

Prefix sums allow computing any subarray sum as a simple difference, reducing the problem from O(n^2) enumeration to a more efficient approach.

What common mistakes cause incorrect counts?

Off-by-one errors, failing to include negative sums, and mismanaging overlapping ranges during merge or binary search are frequent pitfalls.

What constraints affect solution choice?

Large array sizes up to 10^5 and sum ranges up to ±10^5 require O(n log n) methods; naive O(n^2) approaches are infeasible.