Table of Contents

# Count of Range Sum – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.

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 = 2Output:3Explanation: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 = 0Output:1

**Constraints:**

`1 <= nums.length <= 10`

^{5}`-2`

^{31}<= nums[i] <= 2^{31}- 1`-10`

^{5}<= lower <= upper <= 10^{5}- The answer is
**guaranteed**to fit in a**32-bit**integer.

# C++ Count of Range Sum LeetCode Solution

```
``````
class Solution {
public:
int mergeSort(vector<long>& sum, int lower, int upper, int low, int high)
{
if(high-low <= 1) return 0;
int mid = (low+high)/2, m = mid, n = mid, count =0;
count =mergeSort(sum,lower,upper,low,mid) +mergeSort(sum,lower,upper,mid,high);
for(int i =low; i< mid; i++)
{
while(m < high && sum[m] - sum[i] < lower) m++;
while(n < high && sum[n] - sum[i] <= upper) n++;
count += n - m;
}
inplace_merge(sum.begin()+low, sum.begin()+mid, sum.begin()+high);
return count;
}
int countRangeSum(vector<int>& nums, int lower, int upper) {
int len = nums.size();
vector<long> sum(len + 1, 0);
for(int i =0; i< len; i++) sum[i+1] = sum[i]+nums[i];
return mergeSort(sum, lower, upper, 0, len+1);
}
};
```

# Java Count of Range Sum LeetCode Solution

```
``````
class Solution {
private int[] nums;
public int[] sortArray(int[] nums) {
this.nums = nums;
mergeSort(0, nums.length - 1);
return(nums);
}
private void mergeSort(int low, int high) {
if (low >= high) return;
int mid = low + (high - low) / 2;
mergeSort(low, mid);
mergeSort(mid + 1, high);
merge(low, mid, high);
}
private void merge(int low, int mid, int high) {
int[] helper = new int[high - low + 1];
for (int i = low; i <= high; i++) helper[i - low] = nums[i];
int i = low, j = mid + 1;
int idx = low;
while (i <= mid && j <= high) {
if (helper[i - low] < helper[j - low]) {
nums[idx++] = helper[i++ - low];
} else {
nums[idx++] = helper[j++ - low];
}
}
while (i <= mid) {
nums[idx++] = helper[i++ - low];
}
}
}
```

# Python 3 Count of Range Sum LeetCode Solution

```
``````
def countRangeSum(self, nums, lower, upper):
n = len(nums)
Sum, BITree = [0] * (n + 1), [0] * (n + 2)
def count(x):
s = 0
while x:
s += BITree[x]
x -= (x & -x)
return s
def update(x):
while x <= n + 1:
BITree[x] += 1
x += (x & -x)
for i in range(n):
Sum[i + 1] = Sum[i] + nums[i]
sortSum, res = sorted(Sum), 0
for sum_j in Sum:
sum_i_count = count(bisect.bisect_right(sortSum, sum_j - lower)) - count(bisect.bisect_left(sortSum, sum_j - upper))
res += sum_i_count
update(bisect.bisect_left(sortSum, sum_j) + 1)
return res
```

Array-1180

String-562

Hash Table-412

Dynamic Programming-390

Math-368

Sorting-264

Greedy-257

Depth-First Search-256

Database-215

Breadth-First Search-200

Tree-195

Binary Search-191

Matrix-176

Binary Tree-160

Two Pointers-151

Bit Manipulation-140

Stack-133

Heap (Priority Queue)-117

Design-116

Graph-108

Simulation-103

Prefix Sum-96

Backtracking-92

Counting-86

Sliding Window-73

Linked List-69

Union Find-66

Ordered Set-48

Monotonic Stack-47

Recursion-43

Trie-41

Binary Search Tree-40

Divide and Conquer-40

Enumeration-39

Bitmask-37

Queue-33

Memoization-32

Topological Sort-31

Geometry-30

Segment Tree-27

Game Theory-24

Hash Function-24

Binary Indexed Tree-21

Interactive-18

Data Stream-17

String Matching-17

Rolling Hash-17

Shortest Path-16

Number Theory-16

Combinatorics-15

Randomized-12

Monotonic Queue-9

Iterator-9

Merge Sort-9

Concurrency-9

Doubly-Linked List-8

Brainteaser-8

Probability and Statistics-7

Quickselect-7

Bucket Sort-6

Suffix Array-6

Minimum Spanning Tree-5

Counting Sort-5

Shell-4

Line Sweep-4

Reservoir Sampling-4

Eulerian Circuit-3

Radix Sort-3

Strongly Connected Componen-t2

Rejection Sampling-2

Biconnected Component-1

## Leave a comment below