LeetCode 2906: Construct Product Matrix
LeetCode 2906 Solution 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.
LeetCode 2906 Solutions in Java, C++, Python
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;
}
}Interactive Code Editor for LeetCode 2906
Improve Your LeetCode 2906 Solution
Use the editor below to refine the provided solution for LeetCode 2906. Select a programming language and try the following:
- Add import statements if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.
Loading editor...