Yet another std::lower_bound-based C++ solution


  • 1
    K
    class Solution {
    private:
        multimap<int64_t,int> hash; // associating a sum on numbers in the range [0,pos) to pos
        vector<int64_t> sums;       // other way around: associating pos to sum of numbers in the range [0,pos)
    public:
        int countRangeSum(vector<int>& nums, int lower, int upper) {
            // preprocessing step: fill in the association arrays above
            sums.clear();
            hash.clear();
            sums.push_back(0); // make sum[0,0] = sum[0,1) to be 0
            for(int64_t i=0, sum=0; i<nums.size(); i++){
                sum += nums[i];
                sums.push_back( sum );
                hash.insert( pair<int64_t,int>(sum,i+1) );
            }
            // now a sum within an interval [i:j] is just sums[j+1]-sums[i] and it should be between lower-upper
            // to have a quick (log(N)) check for the lower-upper interval we take advantage of ordering in hash
            int retval = 0;
            for(int i=0; i<sums.size(); i++){
                int64_t s = sums[i];
                for( multimap<int64_t,int>::const_iterator it = hash.lower_bound( s + lower ); // find first it that it->first - s >= lower
                       it != hash.end() && it->first - s <= upper; it++ ){ // iterate till end or till it->first - s <= upper 
                   if( it->second > i ) // make sure it is a non-empty range [i,j] with i<j
                       retval++;
                }
            }
            return retval;
        }
    };

  • 0

    @koskot77
    Time complexity of this solution should be O(n^2) at least;
    Look at this part,

    for(int i=0; i<sums.size(); i++){
                int64_t s = sums[i];
                for( multimap<int64_t,int>::const_iterator it = hash.lower_bound( s + lower ); // find first it that it->first - s >= lower
                       it != hash.end() && it->first - s <= upper; it++ ){ // iterate till end or till it->first - s <= upper 
                   if( it->second > i ) // make sure it is a non-empty range [i,j] with i<j
                       retval++;
                }
            }
    

    Even thought you use hash.lower_bound which take log(n), but the size between hash.lower_bound( s + lower ) might be n too.
    Think about {1,1,1,1,1,1,1} range [-1, 100]


  • 0
    K

    @yong-cao-7731
    Yep, in you example my code will take O(N^2) time to complete because there will be total N^2 ranges to count. I don't yet see a simple way to stay with this design and avoid the nested loop. Guess, I'll need another approach here.


Log in to reply
 

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