Problem Statement in English

You’re given a 2D grid of integers. You need to construct a product matrix where each element at position (i, j) is the product of all elements in the original grid except the one at (i, j), and then take the result modulo 12345.

Return the resulting product matrix.

Approach

This problem would have been much easier if instead of a 2D grid, we had a 1D array. In that case, we could have easily calculated the prefix and suffix products and then filled the result array in O(n) time.

So let’s convert this problem into a 1D problem. We can flatten the 2D grid into a 1D array and then calculate the prefix and suffix products for that array. Finally, we can fill the result back into the 2D grid.

And we’re done!

Solution in Python


class Solution:
    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:
        M = len(grid)
        N = len(grid[0])
        MOD = 12345

        flattened = [grid[i][j] for i in range(M) for j in range(N)]
        L = len(flattened)
        
        prefix = [0 for _ in range(L)]
        prefix[0] = flattened[0]
        for i in range(1, L):
            prefix[i] = prefix[i - 1] * flattened[i] % MOD
        
        suffix = [0 for _ in range(L)]
        suffix[-1] = flattened[-1]
        for i in range(L - 2, -1, -1):
            suffix[i] = suffix[i + 1] * flattened[i] % MOD

        for index in range(L):
            r = index // N
            c = index % N

            pre = post = 1
            if 0 <= index - 1:
                pre = prefix[index - 1]
                
            if index + 1 < L:
                post = suffix[index + 1]

            grid[r][c] = (pre * post) % MOD

        return grid

Complexity

  • Time: $O(M \times N)$
    Where M and N are the dimensions of the grid, since we need to iterate through the grid to calculate the prefix and suffix products, and then again to fill the result.

  • Space: $O(M \times N)$
    Where M and N are the dimensions of the grid, since we need to iterate through the grid to calculate the prefix and suffix products, and then again to fill the result.

Mistakes I Made

I messed up the 1D to 2D mapping and ended up with wrong indices for the prefix and suffix arrays. I also forgot to take the modulus at some places, which could lead to integer overflow.

And we are done.