LeetCode Q327: Count of Range Sum (hard)

Given an integer array nums, 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 (i ≤ j), inclusive.

Note:
A naive algorithm of O(n2) is trivial. You MUST do better than that.

Example:
Given nums = [-2, 5, -1], lower = -2, upper = 2,
Return 3.
The three ranges are : [0, 0], [2, 2], [0, 2] and their respective sums are: -2, -1, 2.

Solution 1:

My solution is to pre-processing the array and compute range sum, than build BST for searching. In C++, to allow duplicated nodes in a BST, you should use multimap.

	class Solution {
	public:
	int countRangeSum(vector<int>& _nums, int lower, int upper) {
	int res=0;
	if(_nums.empty())
	return 0;
	vector<long> nums(_nums.size(), 0);
	nums[0]=_nums[0];
	for(int i=1; i<_nums.size(); i++)
	nums[i]=nums[i-1]+long(_nums[i]);
	multimap<long, long> mySet;
	mySet.insert(pair<long, long>(0, -1));
	for(int i=0; i<nums.size(); i++)
	mySet.insert(pair<long, long>(nums[i], i));
	for(int i=0; i<nums.size(); i++){
	auto hiIt = mySet.upper_bound(nums[i]-lower);
	auto lowIt = mySet.lower_bound(nums[i]-upper);
	for(auto it=lowIt; it!=hiIt; it++)
	if((*it).second<i)
	res++;
	}
	return res;
	}
	};

view raw Q327-1.cpp hosted with ❤ by GitHub

Revised version of solution 1

	class Solution {
	public:
	int countRangeSum(vector<int>& _nums, int lower, int upper) {
	int res=0;
	if(_nums.empty())
	return 0;
	vector<long> nums(_nums.size(), 0);
	nums[0]=_nums[0];
	for(int i=1; i<_nums.size(); i++)
	nums[i]=nums[i-1]+long(_nums[i]);
	multiset<long> sets;
	sets.insert(long(INT_MIN)*5);
	for(int i=0; i<nums.size(); i++){
	auto it = sets.lower_bound(nums[i]-upper);
	if(nums[i]>=lower&&nums[i]<=upper)
	res++;
	if(it!=sets.end())
	for(; it!=sets.end()&&nums[i]-*it>=lower; it++)
	res++;
	sets.insert(nums[i]);
	}
	return res;
	}
	};

view raw Q327sol1-ext.cpp hosted with ❤ by GitHub

Solution 2:
Analysis of the solution is given in this post.

	class Solution {
	public:
	int countRangeSum(vector<int>& nums, int lower, int upper) {
	int size=nums.size();
	if(size==0) return 0;
	vector<long> sums(size+1, 0);
	for(int i=0; i<size; i++) sums[i+1]=sums[i]+nums[i];
	return help(sums, 0, size+1, lower, upper);
	}
	/*** [start, end) ***/
	int help(vector<long>& sums, int start, int end, int lower, int upper){
	/*** only-one-element, so the count-pair=0 ***/
	if(end-start<=1) return 0;
	int mid=(start+end)/2;
	int count=help(sums, start, mid, lower, upper)
	+ help(sums, mid, end, lower, upper);
	int m=mid, n=mid, t=mid, len=0;
	/*** cache stores the sorted-merged-2-list ***/
	/*** so we use the "len" to record the merged length ***/
	vector<long> cache(end-start, 0);
	for(int i=start, s=0; i<mid; i++, s++){
	/*** wrong code: while(m<end && sums[m++]-sums[i]<lower); ***/
	while(m<end && sums[m]-sums[i]<lower) m++;
	while(n<end && sums[n]-sums[i]<=upper) n++;
	count+=n-m;
	/*** cache will merge-in-the-smaller-part-of-list2 ***/
	while(t<end && sums[t]<sums[i]) cache[s++]=sums[t++];
	cache[s]=sums[i];
	len=s;
	}
	for(int i=0; i<=len; i++) sums[start+i]=cache[i];
	return count;
	}
	};

view raw 327-2.cpp hosted with ❤ by GitHub