Last updated on March 1st, 2025 at 08:35 pm
Here, we see a Count of Range Sum LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Binary Indexed Tree, Binary Search, Divide and Conquer, Segment, Sort
Companies
Level of Question
Hard
Count of Range Sum LeetCode Solution
Table of Contents
1. 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
2. Coding Pattern Used in Solution
The coding pattern used in all the implementations is “Divide and Conquer with Merge Sort”. The problem is solved by recursively dividing the array into smaller subarrays, solving the problem for each subarray, and then merging the results while counting the valid range sums.
3. Code Implementation in Different Languages
3.1 Count of Range Sum 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;
}
};
3.2 Count of Range Sum 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.3 Count of Range Sum 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;
};
3.4 Count of Range Sum 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))
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n log n) | O(n) |
| Java | O(n2) | O(1) |
| JavaScript | O(n log n) | O(n) |
| Python | O(n log n) | O(n) |
- The C++, JavaScript, and Python implementations use an efficient divide-and-conquer approach with merge sort, resulting in O(n log n) time complexity.
- The Java implementation, however, uses a brute-force approach, leading to O(n²) time complexity.
- The space complexity for all implementations except Java is O(n) due to the use of temporary arrays for merging.