• + 0 comments

    creating the array on the heap

    long int* a = new long int[N+1]();

    makes it O(N+1) instead of O(1) auxiliary space. plus there is a nasty bug in your code. you allocate on the heap and you never deallocate it

    delete a;

    So here is a BETTER solution O(log(N)) time complexity, and O(K) space complexity.

    long arrayManipulation(int n, vector<vector<int>> queries) `{

    long max = LONG_MIN;
    map<int, long> range;
    for(auto el: queries)
    {
    
        int a = el[0];
        int b = el[1]+1;
        int k = el[2];
    
        auto p1 = range.insert(make_pair(a,k));
        if(p1.second == false)
            p1.first->second += k;
    
        auto p2 = range.insert(make_pair(b, -k));
        if( p2.second == false)
            p2.first->second -= k;
    }
    long sum = 0;
    for(auto v:range)
    {
    
        sum += v.second;
        if(max<sum)
            max = sum;
    }
    return max;
    

    }`

    In this Approach, you olnly store the boundaries of each range, no need to fill the inbetween zeros, also searching, inserting and deleting and element in map is O(log(size(map)), which makes the worst case scenario O(log(N)).

    any comment or suggestion is welcome.