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

  • 0
            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];
                return result;

Log in to reply

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