Is Count of Range Sum easy or hard?

Count of Range Sum is classified as a Hard problem because the optimal solution requires combining prefix sums with divide-and-conquer counting. Many candidates initially attempt O(n²) enumeration before recognizing the need for an O(n log n) approach.

Count of Range Sum Python/Java solution

In Python or Java, the typical implementation computes prefix sums and applies a modified merge sort to count valid ranges during the merge phase. The algorithm maintains two pointers in the right half for each left prefix value and counts differences within [lower, upper].

How to solve Count of Range Sum in O(n)?

An exact O(n) solution is not known for the general problem. The best practical approach is O(n log n) using prefix sums with merge sort or balanced data structures such as Binary Indexed Trees or ordered sets to maintain prefix order efficiently.

What is the best approach for Count of Range Sum?

The most efficient approach uses prefix sums combined with a modified merge sort. While sorting the prefix array, the algorithm counts how many prefix differences fall within [lower, upper]. This divide-and-conquer strategy runs in O(n log n) time and O(n) space, which is optimal for large inputs.

Is Count of Range Sum asked at Google/Amazon/Meta?

Count of Range Sum is a classic hard interview problem involving prefix sums and divide-and-conquer counting. Variants of this problem have appeared in interviews at companies like Google, Amazon, and Meta because it tests understanding of advanced array processing and algorithm optimization.

What data structure is used in Count of Range Sum?

The optimized solutions rely on prefix sums along with data structures that maintain sorted order. Common implementations use merge sort, Binary Indexed Trees (Fenwick trees), segment trees, or balanced ordered sets to efficiently count valid prefix ranges.

What is the time complexity of Count of Range Sum?

The optimal algorithm runs in O(n log n) time using a merge-sort-based counting technique on prefix sums. A naive solution that checks every subarray requires O(n²) time, which becomes too slow when the array size grows large.

Description Solution Video 21:05

327. Count of Range Sum

Hard40.3% acceptance5 companies

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 <= 10⁵
-2³¹ <= nums[i] <= 2³¹ - 1
-10⁵ <= lower <= upper <= 10⁵
The answer is guaranteed to fit in a 32-bit integer.

Asked at 5 companies

Morgan Stanley

Google Amazon Meta Oracle

Topics

21:05

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

327. Count of Range Sum

Asked at 5 companies

Topics

Similar problems