Two Step Java Solution with Time Complexity O(k+n)


  • 0
    N
    • Step 1: Update result so that index tells you diff between prev and this element, ie. on start idx, you tell all coming elements need to be incremented by val and on end+1 idx, you tell all coming elements need to be decremented by val : O(k)
    • Step 2: Calculate value at index by finding cumulative sum : O(n)
    • Total Time Complexity : O(k+n)
    public class Solution {
        public int[] getModifiedArray(int length, int[][] updates) {
            int result[] = new int[length];
        for (int[] update : updates) {
                int start = update[0], end = update[1], val = update[2];
                result[start] += val;   // add val on start idx
                if (end < length-1) result[end+1] -= val;   // add -val on end+1 idx
            }
            for (int i = 1; i < result.length; i++) {
                result[i] = result[i-1]+result[i];    // find cummulative sum
            }
            return result;
        }
    }
    

Log in to reply
 

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