Share my accepted java code with explanation O(N+K)


  • 0
    J

    The idea is that, we maintain a current increment, every time we meet a start of update, we add the inc to the total increment, and every time we meet the end of a update, we deduct the inc from the total increment.
    The only trick here is to deduct the inc from total increment at the position of end+1.

    public int[] getModifiedArray(int length, int[][] updates) {
            int[] modified = new int[length];
            if (updates != null && updates.length > 0 && updates[0].length > 0) {
                for (int[] update:updates) {
                    int inc = update[2];
                    int left = update[0];
                    int right = update[1];
                    modified[left] += inc;
                    if (right+1<length) {
                        modified[right+1] += -inc; 
                       //deduct the value after right, because we still need to add inc at the position of right
                    }
                }
                int curr = 0;
                for (int i=0;i<length;i++) {
                    curr += modified[i];
                    modified[i] = curr;
                }
            }
            return modified;
        }

  • 0
    L

    Would you mind explaining the logic in simple english ?


Log in to reply
 

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