O(n) & O(1) cpp solution


  • 0
    P
    class Solution {
    public:
        vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {
            vector<int> ans(length,0);
            for(auto vec:updates){
                ans[vec[0]] += vec[2];
                if(vec[1]+1<length) ans[vec[1]+1] -= vec[2];
            }
            for(int i=0,count=0;i<length;i++){
                count+=ans[i];
                ans[i] = count;
            }
            return ans;
        }
    };
    

  • 0
    I

    This is not O(N), it is O(N + K)


  • 0
    P

    Oh, usually we assume k<=n, there for k+n < 2n. O(k+n) = O(n)


  • 0
    I

    @PKUGoodSpeed You cannot assume it here, since K can be much bigger than the size of the array. You can have 3 elements in the array and 2000 updates each with different range and values.


Log in to reply
 

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