Last updated on October 25th, 2024 at 10:36 pm

Here, We see Count of Range Sum LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Count of Range Sum LeetCode Solution

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.

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

1. Count of Range Sum LeetCode Solution C++

class Solution {
public:
	int countRangeSum(vector<int>& nums, int lower, int upper) {
		if (nums.size() == 0)
			return 0;
		vector<long long> cums(nums.size(), 0);
		cums[0] = nums[0];
		for (int i = 1; i < nums.size(); ++i) 
			cums[i] = cums[i - 1] + nums[i];
		vector<long long> tmp(nums.size());
		return recursive_count(cums, 0, nums.size() - 1, tmp, lower, upper);
	}
	int recursive_count(vector<long long>& cums, int i, int j, vector<long long>& tmp, int lower, int upper) {
		if (i == j)
			return cums[i] >= lower && cums[i] <= upper;
		if (i > j)
			return 0;
		int mid = (i + j) / 2;
		int left = recursive_count(cums, i, mid, tmp, lower, upper);
		int right = recursive_count(cums, mid + 1, j, tmp, lower, upper);
		int p = i, q = i, k = mid + 1;
		int cross = 0;
		for (k = mid + 1; k <= j; ++k) {
			while (p <= mid && cums[k] - cums[p] > upper) 
				++p;
			while (q <= mid && cums[k] - cums[q] >= lower) 
				++q;
			cross += q - p;
		}
		p = i; q = mid + 1; int o = i;
		while (p <= mid || q <= j) {
			long long v1 = (p <= mid ? cums[p] : LONG_MAX);
			long long v2 = (q <= j ? cums[q] : LONG_MAX);
			if (v1 < v2)
				tmp[o++] = cums[p++];
			else
				tmp[o++] = cums[q++];
		}
		copy(tmp.begin() + i, tmp.begin() + j + 1, cums.begin() + i);

		return left + right + cross;
	}
};

2. Count of Range Sum LeetCode Solution Java

class Solution {
public int countRangeSum(int[] nums, int lower, int upper) {
    int n = nums.length;
    long[] sums = new long[n + 1];
    for (int i = 0; i < n; ++i)
        sums[i + 1] = sums[i] + nums[i];
    int ans = 0;
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j <= n; ++j)
            if (sums[j] - sums[i] >= lower && sums[j] - sums[i] <= upper)
                ans++;
    return ans;
}
}

3. Count of Range Sum Solution JavaScript

var countRangeSum = function (nums, lower, upper) {
    let preSum = Array(nums.length + 1).fill(0);
    let count = 0;
    for (let i = 0; i < nums.length; i++) {
        preSum[i + 1] = preSum[i] + nums[i];
    }
    const sort = function (preSum) {
        if (preSum.length === 1) return preSum;
        let mid = Math.floor(preSum.length / 2);
        let left = sort(preSum.slice(0, mid));
        let right = sort(preSum.slice(mid))
        return merge(left, right);
    }
    const merge = function (left, right) {
        let start = 0;
        let end = 0;
        for (let i = 0; i < left.length; i++) {
            while (start < right.length && right[start] - left[i] < lower) {
                start++;
            }
            while (end < right.length && right[end] - left[i] <= upper) {
                end++;
            }
            count += end - start;
        }
        let sort = [];
        while (left.length && right.length) {
            if (left[0] <= right[0]) {
                sort.push(left.shift());
            } else {
                sort.push(right.shift());
            }
        }
        return [...sort, ...left, ...right];
    }
    sort(preSum);
    return count;
};

4. Count of Range Sum Solution Python

class Solution(object):
    def countRangeSum(self, nums, lower, upper):
        first = [0]
        for num in nums:
            first.append(first[-1] + num)
        def sort(lo, hi):
            mid = (lo + hi) / 2
            if mid == lo:
                return 0
            count = sort(lo, mid) + sort(mid, hi)
            i = j = mid
            for left in first[lo:mid]:
                while i < hi and first[i] - left <  lower: i += 1
                while j < hi and first[j] - left <= upper: j += 1
                count += j - i
            first[lo:hi] = sorted(first[lo:hi])
            return count
        return sort(0, len(first))