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


  • 0
    G

    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?

    Thanks a lot in advance.


  • 4
    C

    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


  • 0
    G

    Great! Thanks a lot.


Log in to reply
 

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