Range Addition — LeetCode 370 Python Solution

The problem

You are given an integer length and an array updates where updates[i] = [startIdxi, endIdxi, inci]. You have an array arr of length length with all zeros, and you have some operation to apply on arr.

Example

Input

length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]]

Output

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

Python solution

class Solution:
    def getModifiedArray(self, length: int, updates: List[List[int]]) -> List[int]:
        d = [0] * length
        for l, r, c in updates:
            d[l] += c
            if r + 1 < length:
                d[r + 1] -= c
        return list(accumulate(d))

Complexity

Pattern: Prefix Sum

Precompute running totals once so any range query becomes a single subtraction. LeetCode 370. Range Addition is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Prefix Sum.

The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.

Related problems