Problem Statement in English

You’re given an integer n and a 2D array queries where each queries[i] = [topLeftRow, topLeftCol, bottomRightRow, bottomRightCol] represents a submatrix of an n x n matrix.

Initially, the matrix is filled with all zeros.

Your task is to increment all the elements of each submatrix defined by the queries by one and return the resulting matrix.

Approach

I went for the slightly less efficient but straightforward approach that only uses a difference array for each row. But you could also use a 2D difference array to achieve the same result with slightly better time complexity. Albeit, a little more complex to implement.

The idea is that for each query, we iterate through the rows of the submatrix defined by the query and update the difference array for that row. Specifically, we increment the value at the topLeftCol index and decrement the value at the bottomRightCol + 1 index (if it exists). So it’s just 2 operations per row per query.

I noticed that there are at most 10410^4 queries, and n can be at most 500. So in the worst case, we would be doing 104×500=5×10610^4 \times 500 = 5 \times 10^6 operations which is acceptable.

But if the constraints were larger, we could have used a 2D difference array and ended up with better time complexity.

Solution in Python


class Solution:
    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:
        diffMatrix = [[0 for _ in range(n)] for _ in range(n)]

        for tlr, tlc, brr, brc in queries:
            for row in range(tlr, min(n, brr + 1)):
                diffMatrix[row][tlc] += 1

                if brc + 1 >= n:
                    continue

                diffMatrix[row][brc + 1] -= 1

        resMatrix = [[0 for _ in range(n)] for _ in range(n)]

        for i in range(n):
            acc = 0
            for j in range(n):
                acc += diffMatrix[i][j]
                resMatrix[i][j] = acc

        return resMatrix

Complexity

  • Time: O(q⋅n+n2)O(q \cdot n + n^2)
    Since we process q queries in O(n)O(n) time and then build the result matrix in O(n2)O(n^2) time.

  • Space: O(n2)O(n^2)

And we are done.