Problem

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.

OR

You are given an integer array nums[] of size n, and two integers lower and upper. Your task is to find the number of non-empty contiguous subarrays whose sums lie within the range [lower, upper], inclusive.

Examples

Example 1:

1
2
3

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:

1
2

Input: nums = [0], lower = 0, upper = 0
Output: 1

Solution

Method 1 - Naive

The naive approach involves iterating through all possible subarrays and calculating their sums. For each subarray, we check if the sum lies within the range [lower, upper]. This approach has a time complexity of O(n²) due to the nested iterations over the array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

class Solution {

    public int countRangeSum(int[] nums, int lower, int upper) {
        int n = nums.length;
        int count = 0;

        // Iterate over all starting indices of subarrays
        for (int i = 0; i < n; i++) {
            int currentSum = 0; // Variable to store the sum of the current subarray

            // Iterate over all ending indices for the subarray starting at index i
            for (int j = i; j < n; j++) {
                currentSum += nums[j]; // Add the current element to the subarray's sum

                // Check if the sum lies within the range [lower, upper]
                if (currentSum >= lower && currentSum <= upper) {
                    count++; // Increment count if the sum is valid
                }
            }
        }

        return count;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        // Example 1
        int[] nums1 = { 1, 2, 3 };
        System.out.println(solution.countRangeSum(nums1, 3, 5)); // Output: 3

        // Example 2
        int[] nums2 = { -2, 5, -1 };
        System.out.println(solution.countRangeSum(nums2, -1, 2)); // Output: 4
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution:
    def countRangeSum(self, nums, lower, upper):
        n = len(nums)
        count = 0

        # Iterate over all starting indices of subarrays
        for i in range(n):
            current_sum = 0 # Variable to store the sum of the current subarray
            
            # Iterate over all ending indices for the subarray starting at index i
            for j in range(i, n):
                current_sum += nums[j] # Add the current element to the subarray's sum
                
                # Check if the sum lies within the range [lower, upper]
                if lower <= current_sum <= upper:
                    count += 1 # Increment count if the sum is valid
        
        return count

# Example usage
solution = Solution()

# Example 1
nums1 = [1, 2, 3]
print(solution.countRangeSum(nums1, 3, 5)) # Output: 3

# Example 2
nums2 = [-2, 5, -1]
print(solution.countRangeSum(nums2, -1, 2)) # Output: 4

Complexity

  • ⏰ Time complexity: O(n^2) due to nested loops.
  • 🧺 Space complexity: O(1)

Method 2 - Using cumulative sum

How we can improve? Think that if we were asked for contiguous subarray with sum = a then how would we would have solved it? To improve the solution, let’s consider how we would solve the problem if we were asked to find the number of contiguous subarrays with a sum equal to a. The cumulative sum (cumsum) can be computed while iterating over the array from lower to upper. At each position j, we would check whether there is an earlier position i < j such that the sum of the subarray from i to j equals a. This can be done using cumsum[j] - cumsum[i-1] = a, which simplifies to cumsum[i-1] = cumsum[j] - a. By caching the cumulative sums as we traverse the array, we can efficiently determine if (cumsum[j] - a) has already been seen.

To extend this idea for the range [a, b] instead of a single value, we can use a TreeSet (or a Balanced Binary Search Tree). The O(n log n) solution involves tracking the cumulative sums in a sorted structure. At each position i, if the number itself is within the range [a, b], it is valid. Otherwise, if the cumulative sum at position i falls in the range [a, b], there is a subarray summing to the range from the start to the current position.

To account for subarrays between earlier positions and the current position, using the difference cumsum[j] - S helps check if a subarray from an earlier index sums to S. This can be efficiently tracked using a hash map. For checking the range [a, b], we use a TreeSet to store all cumulative sums seen so far. The number of valid subarrays ending at i can be found using the subset count corresponding to (cumsum[i] - b) and (cumsum[i] - a).

The TreeSet computes subsets efficiently using its subset operations (subSet). For each position, we increment the count by the size of the subset that falls within the range. The implementation ensures efficient operations by avoiding expensive calls like size().

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

class Pair implements Comparable<Pair> {

    int sum;
    int index;

    Pair(int sum, int index) {
        this.sum = sum;
        this.index = index;
    }

    @Override
    public int compareTo(Pair o) {
        if (this.sum == o.sum) {
            return this.index - o.index;
        }
        return this.sum - o.sum;
    }
}

public class Solution {

    public static int countRangeSum(int[] nums, int lower, int upper) {
        int count = 0;
        TreeSet<Pair> treeSet = new TreeSet<>();
        int cumsum = 0;

        for (int i = 0; i < nums.length; i++) {
            cumsum += nums[i];

            // Count single element subarrays within range
            if (nums[i] >= lower && nums[i] <= upper) {
                count++;
            }

            // Count subarrays starting from the first element
            if (cumsum >= lower && cumsum <= upper) {
                count++;
            }

            // Find all valid subsets using cumulative sums
            NavigableSet<Pair> subSet = treeSet.subSet(
                new Pair(cumsum - upper, i + 1),
                true,
                new Pair(cumsum - lower, i + 1),
                false
            );

            if (!subSet.isEmpty()) {
                count +=
                Math.abs(subSet.first().index - subSet.last().index) + 1;
            }

            // Add current cumulative sum to the TreeSet
            treeSet.add(new Pair(cumsum, i));
        }

        return count;
    }

    public static void main(String[] args) {
        int[] nums1 = { 1, 2, 3 };
        System.out.println(countRangeSum(nums1, 3, 5)); // Output: 3

        int[] nums2 = { -2, 5, -1 };
        System.out.println(countRangeSum(nums2, -1, 2)); // Output: 4
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution:
    def countRangeSum(self, nums, lower, upper):
        count = 0
        sorted_list = SortedList()
        cumsum = 0

        for i, num in enumerate(nums):
            cumsum += num

            # Count single element subarrays within range
            if lower <= num <= upper:
                count += 1

            # Count subarrays starting from the beginning
            if lower <= cumsum <= upper:
                count += 1

            # Find all valid subsets using cumulative sums
            start = sorted_list.bisect_lower(cumsum - upper)
            end = sorted_list.bisect_upper(cumsum - lower)
            count += (end - start)

            # Add the current cumulative sum to the sorted list
            sorted_list.add(cumsum)

        return count

# Example usage:
solution = Solution()
nums1 = [1, 2, 3]
print(solution.countRangeSum(nums1, 3, 5))  # Output: 3

nums2 = [-2, 5, -1]
print(solution.countRangeSum(nums2, -1, 2))  # Output: 4

Complexity

  • ⏰ Time complexity: O(n log n), due to the TreeSet operations for subset queries.
  • 🧺 Space complexity: O(n) for storing cumulative sums.

Method 3 - Merge Sort

Recall the problem where we counted the number of smaller elements on the upper of each element. Read more here: Count Inversions - Count Smaller on Right. The task involved counting occurrences of x[j] < x[i], for j > i, or equivalently, x[j] - x[i] < 0 for j > i. In the range sum problem, the goal is to count occurrences where a ≤ (x[j] - x[i]) ≤ b for j > i.

This problem can be solved in a similar way to the “count smaller elements on upper” problem, using merge sort. The solution has a complexity of O(n log n) and counts the valid ranges during the merge step. In the merge stage, the lower half [start, mid) and upper half [mid, end) are already sorted. Then, for each index i in the lower half, we locate two indices sl and su in the upper half:

  • sl marks the first index where S[j] - S[i] > upper.
  • su marks the first index where S[k] - S[i] ≥ lower.

The subarray sums within [lower, upper] are counted as su - sl. To merge the arrays, we use an auxiliary array merged[].

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

class Solution {

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

    private int mergeSortCount(
        long[] prefix,
        int start,
        int end,
        int lower,
        int upper
    ) {
        if (start >= end) return 0;

        int mid = (start + end) / 2;
        int ans =
            mergeSortCount(prefix, start, mid, lower, upper) +
            mergeSortCount(prefix, mid + 1, end, lower, upper);

        int i = start, j = start, k = 0;
        long[] temp = new long[end - start + 1];
        for (int right = mid + 1; right <= end; right++) {
            while (i <= mid && prefix[right] - prefix[i] > upper) i++;
            while (j <= mid && prefix[right] - prefix[j] >= lower) j++;
            ans += j - i;

            while (k <= mid && prefix[k] <= prefix[right]) temp[k - start] =
                prefix[k++];
            temp[k - start] = prefix[right];
            k++;
        }

        System.arraycopy(temp, 0, prefix, start, end - start + 1);
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution:
    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
        prefix = [0] * (len(nums) + 1)
        for i in range(len(nums)):
            prefix[i + 1] = prefix[i] + nums[i]
        return self._merge_sort_count(prefix, 0, len(prefix) - 1, lower, upper)

    def _merge_sort_count(self, prefix: List[int], start: int, end: int, lower: int, upper: int) -> int:
        if start >= end:
            return 0
        
        mid = (start + end) // 2
        ans = (self._merge_sort_count(prefix, start, mid, lower, upper) +
            self._merge_sort_count(prefix, mid + 1, end, lower, upper))
        
        i = j = start
        temp = []
        for right in range(mid + 1, end + 1):
            while i <= mid and prefix[right] - prefix[i] > upper:
                i += 1
            while j <= mid and prefix[right] - prefix[j] >= lower:
                j += 1
            ans += j - i

            while len(temp) <= mid - start and prefix[start + len(temp)] <= prefix[right]:
                temp.append(prefix[start + len(temp)])
            temp.append(prefix[right])
        
        prefix[start: end + 1] = temp
        return ans

Complexity

  • ⏰ Time complexity: O(n log n) for merge sort and range counting during merging.
  • 🧺 Space complexity: O(n) for the auxiliary merged array used during merges.