# Why is the C++ implementation LTE while Java implementation (of the same algorithm) Accepted?

• I translated the algorithm presented at https://leetcode.com/discuss/79083/share-my-solution in C++ as below.

``````class Solution {
public:
int countRangeSum(vector<int>& nums, int lower, int upper) {
int n = nums.size();
vector< double > sums( n+1, 0 );
for( int i=0; i<n; i++ ){
sums[i+1] = sums[i] + nums[ i ];
}
return merge_s( sums, 0, n+1, lower, upper );
}
private:
int merge_s( vector<double> sums, int start, int end, int lower,int upper ){
if( end - start <= 1 ){
return 0;
}

int mid = (start + end) / 2;
int count = merge_s( sums, start, mid, lower, upper ) + merge_s( sums, mid, end, lower, upper );
int j = mid;
int k = mid;
int t = mid;

vector< double > cache( end - start );
for( int i = start, r = 0; i < mid; ++i, ++r ){
while(  k < end && sums[ k ] - sums[ i ] < lower ){
k++;
}
while( j < end && sums[ j ] - sums[ i ] <= upper ){
j++;
}
while( t < end && sums[ t ] < sums[ i ] ){
cache[ r++ ] = sums[ t++ ];
}
cache[ r ] = sums[ i ];
count += j - k;
}

memcpy( &sums[0]+start, &cache[0], ( t - start ) * sizeof( double) );
/*
for( int i=0; i < t - start; i++ ){
sums[ start + i ] = cache[ i ];
}
*/
return count;
}
};
``````

The OJ result is

``````Submission Result: Time Limit Exceeded

Last executed input:
[28,26,22,7,12,-26,25,11,-14,0,0,6,20,4,17,-7,4,-14,-19,-16,8,-21,-26,24,-29,-18,-13,2,-16,-14,-26,-14, ...// more numbers follow]
1
4
``````

But the JAVA version at the above link is Accepted.

Can anybody tell me what is wrong/inefficient in my C++ implementation?

• Hello,

It's because of vector<double> sums in the recursive function. If you have the parameter this way then recursive calls will copy the vector using the copy constructor of std::vector<double>. This means that a lot of allocations are made.

The solution for this problem is to have the parameter as vector<double>& instead of vector<double>. This will avoid creating a new instance of the sum vector at each recursive call.

Cosmin

• Great! Thanks a lot.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.