Count of Range Sum

Problem Statement

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.

Examples

Example 1:

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

Explanation:
The three subarrays whose sum lies in range of -2 to 2 are:
index[0] = [-2] with sum = -2
index[2] = [-1] with sum = -1
index[0, 1, 2] = [-2, 5, -1] with sum = 2

Example 2:

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

Explanation:
There is only one subarray [0], and its sum is 0, which lies within [0, 0] range.

Different Approaches

1️⃣ Brute Force Approach

Intuition:

We calculate the sum of all possible subarrays using two nested loops and count the ones that lie within the given range [lower, upper].

Code:

#include <iostream>
#include <vector>
using namespace std;

int countRangeSum(vector<int>& nums, int lower, int upper) {
    int n = nums.size();
    int count = 0;
    
    for (int i = 0; i < n; ++i) {
        long long sum = 0;
        for (int j = i; j < n; ++j) {
            sum += nums[j];
            if (sum >= lower && sum <= upper) {
                count++;
            }
        }
    }
    return count;
}

int main() {
    vector<int> nums = {-2, 5, -1};
    int lower = -2, upper = 2;
    cout << countRangeSum(nums, lower, upper) << endl; // Output: 3
    return 0;
}

Complexity Analysis:

• Time Complexity: O(n^2)
  • As there are two nested loops for subarrays sums.
• Space Complexity: O(1)
  • No extra data structure is used.

2️⃣ Divide and Conquer Approach