Construct Product Matrix

Problem Description

Given a 0-indexed 2D integer matrix grid of size n * m, we define a 0-indexed 2D matrix p of size n * m as the product matrix of grid if the following condition is met:

• Each element p[i][j] is calculated as the product of all elements in grid except for the element grid[i][j]. This product is then taken modulo 12345.

Return the product matrix of grid.

Key Insights

• Each element in the product matrix is the product of all other elements in the input matrix.
• Directly calculating the product for each element leads to a time complexity of O(n * m * (n * m)), which is not feasible for large matrices.
• Instead, we can compute the total product of the entire matrix and then for each element, divide this total product by the element at that position.
• Since we need the result modulo 12345, we need to handle cases where an element is zero to avoid division errors.

Space and Time Complexity

Time Complexity: O(n * m)
Space Complexity: O(1) (excluding the output matrix)

Solution

To solve the problem, we will:

1. Calculate the total product of all elements in the input matrix grid.
2. Iterate through each element of the matrix and calculate the product for the corresponding position in the result matrix by dividing the total product by the current element, while taking care of modulo 12345.
3. Handle cases where an element is zero by setting the corresponding product to zero.

The algorithm primarily uses a single pass to compute the total product and another pass to compute the product matrix, making it efficient.

Code Solutions