Java O(K + N)time complexity Solution


  • 131
    L

    Just store every start index for each value and at end index plus one minus it

    for example it will look like:

    [1 , 3 , 2] , [2, 3, 3] (length = 5)

    res[ 0, 2, ,0, 0 -2 ]

    res[ 0 ,2, 3, 0, -5]

    sum 0, 2, 5, 5, 0

    res[0, 2, 5, 5, 0]

     public int[] getModifiedArray(int length, int[][] updates) {
    
        int[] res = new int[length];
         for(int[] update : updates) {
            int value = update[2];
            int start = update[0];
            int end = update[1];
            
            res[start] += value;
            
            if(end < length - 1)
                res[end + 1] -= value;
            
        }
        
        int sum = 0;
        for(int i = 0; i < length; i++) {
            sum += res[i];
            res[i] = sum;
        }
        
        return res;
    }

  • 0
    M

    great idea!!!!!!!


  • 3
    L

    thank you !!!!!!!!!


  • 1

    great answer! a little optimized:

    public int[] getModifiedArray(int length, int[][] updates) {
      if (length < 0 || updates == null || updates.length == 0) return null;
      if (updates[0] == null || updates[0].length != 3) return null;
    
      int[] modified = new int[length];
      for (int[] upd : updates) {
        modified[upd[0]] += upd[2];
        if (upd[1] < length -1)
          modified[upd[1] + 1] -= upd[2];
      }
    
      int sum = 0;
      for (int i = 0; i < length; i++) {
        sum += modified[i];
        modified[i] = sum;
      }
    
      return modified;
    }

  • 1
    L

    GREATE !!!!!!


  • 1
    G

    great idea!!


  • 17
    R

    Just explain res->sum:

    res[0,2,3,0,-5]:

    sum[0] = res[0] = 0;

    sum[1] = res[0] + res[1] = 0 + 2 = 2;

    sum[2] = res[0] + res[1] + res[2] = 0 + 2 + 3 = 5;

    sum[3] = res[0] + res[1] + res[2] + res[3] = 0 + 2 + 3 + 0 = 5;

    sum[4] = res[0] + res[1] + res[2] + res[3] + res[4] = 0 + 2 + 3 + 0 + (-5) = 0;

    sum[0,2,5,5,0]


  • 0
    L

    nice explanation!@


  • 0
    C

    nice tags!!!!!


  • 6
    L

    a little bit optimization.

    for(int i = 1; i < length; i++) {
    res[i] += res[i - 1];
    }


  • 51
    D

    Great solution. Though the code looks simple enough, it took me some time to figure out why exactly we do what we do here. We update the value at start index, because it will be used in the future when we are adding up the values for the sum at each index between start index and end index (both inclusive). We update the negative value at the end index + 1, because the positive value of it should be only added at its previous indices (from start index to end index). Thus, when we accumulate the sum at the end for each index, we will get the correct values for each index. If the end index is the last index in the resulting array, we don't have to do the end index + 1 part, because there is no more index after the last index and there will be no error when we accumulate the sum. Hope I explain it well enough to help others understand!

    Thanks.


  • 1
    C

    great idea


  • 1
    L

    @larrywang2014 nice optimization


  • 2
    A

    @dianhua1560 your explanation is amazing. I wish all those who post solutions could explain it as well as you did :)


  • 1
    L

    @acheiver thanks! :)


  • 0

    "Just store every start index for each value and at end index plus one minus it"
    your written english is reckless
    Excellent idea, terrible explanation ...


  • 5
    M

    Discrete-Time Signal Processing

    • First pass: taking the differentiation of the updates
      => finding out the value change(pulse) over indiex positions(time series)
    • Second pass: taking the integral of the value changes
      => finding out the accumulation of the value changes(pulses) over index positions(time series)

    Attaching a graph to help people understand
    https://en.wikipedia.org/wiki/Discrete-time_signal
    special thanks to @alfred-huang-319 and @shogunsea


  • 5
    B

    Thanks for your excellent answer.

    For this part

    int sum = 0;
        for(int i = 0; i < length; i++) {
            sum += res[i];
            res[i] = sum;
        }
    

    It could be done in this way as well:

    for(int i = 0; i < length-1; i++) {
       result[i+1] = result[i+1] + result[i];
    }
    

  • 0
    P

    @dianhua1560 Thanks for explaining in detail. but why do we take this approach?


  • 0
    L

    So concise, thank you!!


Log in to reply
 

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