[10-line Python 232ms beats 100%] + [how to approach this problem]


  • 0
    M
    '''
    Take a look at the example:
    |  0  |  0  |  0  |  0  |  0  |
    |     |  2  |     |  2  |     |
    |     |     |  3  |     |  3  |
    | -2  |     | -2  |     |     |
    
    At first, it was like:
    Index 0  :  -2 comes, so the sum is -2
    Index 1  :  2 comes, so the sum is 0
    Index 2  :  3 comes, so the sum is 3
    Index 3  :  -2 leaves, so the sum is 5
    Index 4  :  2 leaves, so the sum is 3
    
    Therefore the answer is [-2, 0, 3, 5, 3]
    
    The problem is, at Index 3, how do we know that -2 leaves?
                    at Index 4, how do we know that 2 leaves?
                    
    Here comes the key:
    -2 leaves at Index 3 == From Index 3 on, 2 comes
    2 leaves at Index 4  == From Index 4 on, -2 comes
    
    So the table will look like:
    |  0  |  0  |  0  |  0  |  0  |
    |     |  2  |     |     | -2  |
    |     |     |  3  |     |     |  -3  |
    | -2  |     |     |  2  |     |
    
    Index 0  :  -2 comes, so the sum is -2
    Index 1  :  2 comes, so the sum is 0
    Index 2  :  3 comes, so the sum is 3
    Index 3  :  2 comes, so the sum is 5
    Index 4  :  -2 comes, so the sum is 3
    
    Therefore the answer is [-2, 0, 3, 5, 3]
    '''
    class Solution(object):
        def getModifiedArray(self, length, updates):
            """
            :type length: int
            :type updates: List[List[int]]
            :rtype: List[int]
            """
            result = [0 for i in xrange(length)]
            for update in updates:
                start, end, inc = update[0], update[1], update[2]
                result[start] += inc
                if end + 1 < length:
                    result[end + 1] -= inc
            for i in xrange(1, length):
                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.