Last updated on July 20th, 2024 at 04:21 am
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
Topics
Binary Indexed Tree, Binary Search, Divide and Conquer, Segment, Sort
Companies
Level of Question
Hard
![Count of Range Sum LeetCode Solution](https://i0.wp.com/totheinnovation.com/wp-content/uploads/2024/02/LeetCode-Problem-Solution.png?resize=200%2C200&ssl=1)
Count of Range Sum LeetCode Solution
Table of Contents
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))