Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Imagine reading the matrix in row-major order. The product excluding one cell is the product of everything before it multiplied by the product of everything after it. This avoids division, which would be unsafe when a value has no multiplicative inverse modulo 12345.

Approach

Allocate the result matrix and scan from top-left to bottom-right. Maintain a running product initially equal to one. Write it into the current result cell before multiplying it by the current grid value, reducing modulo 12345. Each result cell now contains its exclusive prefix product.

Scan in reverse row-major order with a second running product. Multiply each stored prefix by this exclusive suffix, then include the current grid value in the suffix. The two factors cover every other cell exactly once. Zero residues need no special treatment because ordinary modular multiplication already handles them, even though the input values are positive.

class Solution:
    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:
        MOD = 12345
        n = len(grid)
        m = len(grid[0])
        res = [[1] * m for _ in range(n)]

        p = 1
        for i in range(n):
            for j in range(m):
                res[i][j] = p
                p = (p * grid[i][j]) % MOD
        
        s = 1
        for i in range(n - 1, -1, -1):
            for j in range(m -1, -1, -1):
                res[i][j] = (s * res[i][j]) % MOD
                s = (s * grid[i][j]) % MOD
        
        return res

Complexity analysis

Let r and c be the grid dimensions. Time: O(r * c). Auxiliary space: O(1) excluding the O(r * c) returned matrix, which is reused for prefix products.