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 = 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
Constraints:
1 <= nums.length <= 105-231 <= nums[i] <= 231 - 1-105 <= lower <= upper <= 105- 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
