Python solution with explanation by example


  • 1
    Y
    class Solution(object):
        def getModifiedArray(self, length, updates):
            """
            :type length: int
            :type updates: List[List[int]]
            :rtype: List[int]
            """
            arr = [0 for i in range(length+1)]
            for lst in updates:
                arr[lst[0]] += lst[2]
                arr[lst[1]+1] -= lst[2] 
            
            for i in range(1,len(arr)-1):
                arr[i] += arr[i-1]
            return arr[0:-1]
    

    Explaination:

    Consider the trick first, for the updates information, we continuously accumulate each inc to it's [start] position and -inc to it's [end+1] position. Then in the final step, we generate those element one after another by doing something like [current] + [current-1].

    Well, maybe some can understand this procedure immediately, but I'm not one of them, took me some time: Imagine a hand write ToDo list, we have a few missions to do, and we only record when to start and when to end. Then after some days, we got the list finished. Now consider the day we have been through, when encounter a start time of a mission, from that day on, we do that mission everyday just like the day before until we meet the corresponding end time. Likewise, for other mission , we have exactly the same procedure and they are totally independent. When we have checked everything on that ToDo list, apparently we got all missions finished, which is corresponding to the status of our result after applying those updates in Range Addition Problem.

    I hope this can be helpful to you.


Log in to reply
 

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