[Solved] Construct Product Matrix C++, Java, Python

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.

Example 1:Input: grid = [[1,2],[3,4]] Output: [[24,12],[8,6]] Explanation: p[0][0] = grid[0][1] * grid[1][0] * grid[1][1] = 2 * 3 * 4 = 24 p[0][1] = grid[0][0] * grid[1][0] * grid[1][1] = 1 * 3 * 4 = 12 p[1][0] = grid[0][0] * grid[0][1] * grid[1][1] = 1 * 2 * 4 = 8 p[1][1] = grid[0][0] * grid[0][1] * grid[1][0] = 1 * 2 * 3 = 6 So the answer is [[24,12],[8,6]].

Example 2:Input: grid = [[12345],[2],[1]] Output: [[2],[0],[0]] Explanation: p[0][0] = grid[0][1] * grid[0][2] = 2 * 1 = 2. p[0][1] = grid[0][0] * grid[0][2] = 12345 * 1 = 12345. 12345 % 12345 = 0. So p[0][1] = 0. p[0][2] = grid[0][0] * grid[0][1] = 12345 * 2 = 24690. 24690 % 12345 = 0. So p[0][2] = 0. So the answer is [[2],[0],[0]].

Constraints:

• 1 <= n == grid.length <= 105
• 1 <= m == grid[i].length <= 105
• 2 <= n * m <= 105
• 1 <= grid[i][j] <= 109

Solution

Python

class Solution:
    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:
        
        it_fwd = (elem for row in grid for elem in row)
        it_rev = (elem for row in reversed(grid) for elem in reversed(row))
        
        prefix = list(accumulate(it_fwd, lambda x, y: (x * y) % 12345, initial=1))
        suffix = list(accumulate(it_rev, lambda x, y: (x * y) % 12345, initial=1))

        m,n = len(grid), len(grid[0])
        for i,j in product(range(m), range(n)):
            k = i * n + j
            grid[i][j] = (prefix[k] * suffix[-k-2]) % 12345
        
        return grid

C++

class Solution {
public:
    vector<vector<int>> constructProductMatrix(vector<vector<int>>& grid) {
        const int mod = 12345; // Define the modulo constant.
        int n = grid.size(); // Get the number of rows in the grid.
        int m = grid[0].size(); // Get the number of columns in the grid.
        vector<vector<int>> Ans = grid; // Create a result matrix and initialize it with the grid values.

        // Initialize the result matrix elements to 1.
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                Ans[i][j] = 1;
            }
        }

        long long Mul = 1; // Initialize a variable to keep track of the cumulative product.

        // Calculate the product of elements in the forward direction (left to right, top to bottom).
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                (Ans[i][j] *= Mul) %= mod; // Multiply the element with the cumulative product and apply modulo.
                (Mul *= grid[i][j]) %= mod; // Update the cumulative product.
            }
        }

        Mul = 1; // Reset the cumulative product to 1.

        // Calculate the product of elements in the reverse direction (right to left, bottom to top).
        for (int i = n - 1; i >= 0; i--) {
            for (int j = m - 1; j >= 0; j--) {
                (Ans[i][j] *= Mul) %= mod; // Multiply the element with the cumulative product and apply modulo.
                (Mul *= grid[i][j]) %= mod; // Update the cumulative product.
            }
        }

        return Ans; // Return the product matrix.
    }
};

Java

import java.util.Arrays;

public class Solution {
    public int[][] constructProductMatrix(int[][] grid) {
        final int mod = 12345;
        int n = grid.length;
        int m = grid[0].length;
        int[][] Ans = new int[n][m];

        // Initialize the result matrix elements to 1.
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                Ans[i][j] = 1;
            }
        }

        long Mul = 1; // Initialize a variable to keep track of the cumulative product.

        // Calculate the product of elements in the forward direction (left to right, top to bottom).
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                Ans[i][j] = (int) (Ans[i][j] * Mul % mod); // Multiply the element with the cumulative product and apply modulo.
                Mul = Mul * grid[i][j] % mod; // Update the cumulative product.
            }
        }

        Mul = 1; // Reset the cumulative product to 1.

        // Calculate the product of elements in the reverse direction (right to left, bottom to top).
        for (int i = n - 1; i >= 0; i--) {
            for (int j = m - 1; j >= 0; j--) {
                Ans[i][j] = (int) (Ans[i][j] * Mul % mod); // Multiply the element with the cumulative product and apply modulo.
                Mul = Mul * grid[i][j] % mod; // Update the cumulative product.
            }
        }

        return Ans; // Return the product matrix.
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] grid = {
            {1, 2, 3},
            {4, 5, 6},
            {7, 8, 9}
        };
        int[][] result = solution.constructProductMatrix(grid);
        for (int[] row : result) {
            System.out.println(Arrays.toString(row));
        }
    }
}

Happy Learning – If you require any further information, feel free to contact me.