Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

A rectangle increment can be represented by four corner changes whose two-dimensional prefix sums activate the update inside the rectangle and cancel it outside. This avoids visiting every affected cell for each query.

Approach

Allocate an (n + 1)-square difference matrix. For inclusive rectangle (r1, c1) through (r2, c2), add at the top-left and just beyond the bottom-right, and subtract just below the left boundary and just right of the top boundary. Reconstruct the n-square answer by adding the prefix above and left, subtracting their overlapping diagonal prefix, and adding the current difference. Extra boundary cells allow updates ending at the grid edge without special cases.

class Solution:
    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:
        m = [[0] * n for _ in range(n)]
        d = [[0] * (n + 1) for _ in range(n + 1)]

        for r1, c1, r2, c2 in queries:
            d[r1][c1] += 1 # start
            d[r2 + 1][c1] -= 1 # stop v
            d[r1][c2 + 1] -= 1 # sop h
            d[r2 + 1][c2 + 1] += 1 # fix diagonal

        for i in range(n):
            for j in range(n):
                ac = m[i - 1][j] if i > 0 else 0
                ar = m[i][j - 1] if j > 0 else 0
                diag = m[i - 1][j - 1] if i > 0 and j > 0 else 0
                m[i][j] = d[i][j] + ac + ar - diag # current effect + acc

        return m

Complexity analysis

Let q = queries.length. Time: O(q + n^2) for four-corner difference updates and one 2-D prefix reconstruction. Auxiliary space: O(n^2) for the difference matrix, in addition to the O(n^2) returned matrix.