LeetCode 2906: Construct Product Matrix Solution

Master LeetCode problem 2906 (Construct Product Matrix), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2906. Construct Product Matrix

Medium

Array Matrix Prefix Sum

Problem Explanation

Explanation

To construct the product matrix, we need to calculate the product of all elements in the original matrix except for the element itself. We can achieve this by first calculating the total product of all elements in the matrix. Then for each element in the matrix, we divide the total product by the element itself and take the modulo to get the value for the product matrix.

Calculate the total product of all elements in the matrix.
For each element in the matrix, calculate the product matrix value by dividing the total product by the element itself and taking the modulo.

Time complexity: O(n * m) where n is the number of rows and m is the number of columns in the matrix. Space complexity: O(1) excluding the output matrix.

Solution Code

class Solution {
    public int[][] constructProductMatrix(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        long totalProduct = 1;
        int[][] result = new int[n][m];
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                totalProduct = (totalProduct * grid[i][j]) % 12345;
            }
        }
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                result[i][j] = (int)((totalProduct * modInverse(grid[i][j], 12345)) % 12345);
            }
        }
        
        return result;
    }
    
    private long modInverse(long a, long m) {
        long m0 = m;
        long y = 0, x = 1;
 
        if (m == 1) {
            return 0;
        }
 
        while (a > 1) {
            long q = a / m;
            long t = m;
 
            m = a % m;
            a = t;
            t = y;
 
            y = x - q * y;
            x = t;
        }
 
        if (x < 0) {
            x += m0;
        }
 
        return x;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2906 (Construct Product Matrix)?

This page provides optimized solutions for LeetCode problem 2906 (Construct Product Matrix) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2906 (Construct Product Matrix)?

The time complexity for LeetCode 2906 (Construct Product Matrix) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2906 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2906 in Java, C++, or Python.

Back to LeetCode Solutions