Line sweep C++ O(n+k) time and O(1) space


  • 0
    L
            vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {
                vector<int> result (length+1, 0); //allocate one extra for endIdx+1
                
                for (auto update: updates) {
                    result[update[0]] += update[2];
                    result[update[1]+1] += -update[2];
                }
                
    //line sweep
                for (int i=1; i<length;i++) {
                    result[i] += result[i-1];
                }
                result.pop_back();
                return result;
        }

Log in to reply
 

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