Count of Range Sum

HARD

Description

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.

Approaches

Checkout 3 different approaches to solve Count of Range Sum. Click on different approaches to view the approach and algorithm in detail.

Brute Force with Prefix Sums

This approach is a straightforward improvement over the naive O(n^3) method. The core idea is to first compute the prefix sums of the input array. The sum of any range [i, j] can then be calculated in O(1) time as prefixSum[j+1] - prefixSum[i]. We can then iterate through all possible start and end indices (i, j) and check if their range sum falls within [lower, upper].

Algorithm

Create a long array prefix of size n + 1 and initialize prefix[0] = 0.
Iterate from i = 0 to n-1, calculating prefix[i+1] = prefix[i] + nums[i].
Initialize count = 0.
Use a nested loop. The outer loop for i from 0 to n-1.
The inner loop for j from i to n-1.
Calculate sum = prefix[j+1] - prefix[i].
If sum >= lower && sum <= upper, increment count.
Return count.

First, we create a prefix sum array, let's call it prefix, of size n+1. We use long for the prefix sums to prevent potential integer overflow, as the sum of up to 10^5 numbers can exceed the int range. prefix[0] is initialized to 0. We populate this array such that prefix[k] stores the sum of the first k elements of nums. So, prefix[k] = nums[0] + ... + nums[k-1]. Then, we use two nested loops to iterate through all possible subarrays. The outer loop iterates from i = 0 to n-1 (the start of the range), and the inner loop iterates from j = i to n-1 (the end of the range). For each pair (i, j), we calculate the range sum S(i, j) using prefix[j+1] - prefix[i]. We check if this sum is between lower and upper, inclusive. If it is, we increment a counter. After checking all pairs, the counter holds the total number of valid range sums.

public int countRangeSum(int[] nums, int lower, int upper) {
    int n = nums.length;
    long[] prefix = new long[n + 1];
    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }

    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            long sum = prefix[j + 1] - prefix[i];
            if (sum >= lower && sum <= upper) {
                count++;
            }
        }
    }
    return count;
}

Complexity Analysis

Time Complexity: O(n^2). The two nested loops run `n * (n+1) / 2` times, leading to a quadratic time complexity. This will be too slow for `n = 10^5`.Space Complexity: O(n). We need an additional array of size `n+1` to store the prefix sums.

Pros and Cons

Pros:

Simple to understand and implement.
Improves upon the O(n^3) naive solution.

Cons:

Inefficient for large inputs and will result in a "Time Limit Exceeded" error for the given constraints.

Code Solutions

Checking out 3 solutions in different languages for Count of Range Sum. Click on different languages to view the code.

class BinaryIndexedTree { private int n ; private int [] c ; public BinaryIndexedTree ( int n ) { this . n = n ; this . c = new int [ n + 1 ]; } public void update ( int x , int v ) { while ( x <= n ) { c [ x ] += v ; x += x & - x ; } } public int query ( int x ) { int s = 0 ; while ( x != 0 ) { s += c [ x ]; x -= x & - x ; } return s ; } } class Solution { public int countRangeSum ( int [] nums , int lower , int upper ) { int n = nums . length ; long [] s = new long [ n + 1 ]; for ( int i = 0 ; i < n ; ++ i ) { s [ i + 1 ] = s [ i ] + nums [ i ]; } long [] arr = new long [ n * 3 + 3 ]; for ( int i = 0 , j = 0 ; i <= n ; ++ i , j += 3 ) { arr [ j ] = s [ i ]; arr [ j + 1 ] = s [ i ] - lower ; arr [ j + 2 ] = s [ i ] - upper ; } Arrays . sort ( arr ); int m = 0 ; for ( int i = 0 ; i < arr . length ; ++ i ) { if ( i == 0 || arr [ i ] != arr [ i - 1 ]) { arr [ m ++] = arr [ i ]; } } BinaryIndexedTree tree = new BinaryIndexedTree ( m ); int ans = 0 ; for ( long x : s ) { int l = search ( arr , m , x - upper ); int r = search ( arr , m , x - lower ); ans += tree . query ( r ) - tree . query ( l - 1 ); tree . update ( search ( arr , m , x ), 1 ); } return ans ; } private int search ( long [] nums , int r , long x ) { int l = 0 ; while ( l < r ) { int mid = ( l + r ) >> 1 ; if ( nums [ mid ] >= x ) { r = mid ; } else { l = mid + 1 ; } } return l + 1 ; } }

Video Solution

Watch the video walkthrough for Count of Range Sum

Algorithms:

Binary SearchDivide and ConquerMerge Sort

Data Structures:

ArrayBinary Indexed TreeSegment TreeOrdered Set

Companies:

Morgan Stanley |