Construct Product Matrix
MedPrompt
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 ingridexcept for the elementgrid[i][j]. This product is then taken modulo12345.
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 <= 1051 <= m == grid[i].length <= 1052 <= n * m <= 1051 <= grid[i][j] <= 109
Approaches
2 approaches with complexity analysis and trade-offs.
A straightforward approach is to iterate through each cell of the output matrix p. For each cell p[i][j], we calculate the required product by iterating through the entire input grid again, multiplying all elements except for grid[i][j].
Algorithm
- Get the dimensions
nandmof thegrid. - Create a new result matrix
pof sizen x m. - Iterate through each cell
(i, j)of thegridfrom(0, 0)to(n-1, m-1).- Initialize a variable
productto 1. - Iterate through each cell
(r, c)of thegridfrom(0, 0)to(n-1, m-1).- If
r != iorc != j, then:product = (product * grid[r][c]) % 12345.
- If
- Set
p[i][j] = product.
- Initialize a variable
- Return
p.
Walkthrough
This method directly translates the problem definition into code. We initialize an n x m result matrix p. We then use a pair of nested loops to visit each target cell (i, j) in p. Inside these loops, we initialize a product variable to 1. Another pair of nested loops iterates through every cell (r, c) in the grid. If the current cell (r, c) is not the same as the target cell (i, j), we multiply its value grid[r][c] into our product. To prevent integer overflow and adhere to the problem's requirement, we perform the modulo operation with 12345 after each multiplication. After the inner loops complete, the product holds the desired value for p[i][j], which we then assign. This process is repeated for all cells (i, j).
class Solution { public int[][] constructProductMatrix(int[][] grid) { int n = grid.length; int m = grid[0].length; int[][] p = new int[n][m]; int mod = 12345; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { long product = 1; for (int r = 0; r < n; r++) { for (int c = 0; c < m; c++) { if (r != i || c != j) { product = (product * grid[r][c]) % mod; } } } p[i][j] = (int) product; } } return p; }}Complexity
Time
O((n*m)^2) or O(N^2), where N is the total number of elements. For each of the `N` elements in the output matrix, we iterate through all `N` elements of the input grid.
Space
O(n*m) or O(N), where N is the total number of elements. This space is required to store the resulting product matrix `p`.
Trade-offs
Pros
Simple to understand and implement.
Cons
Extremely inefficient due to its O((n*m)^2) time complexity.
Will result in a 'Time Limit Exceeded' error for the given constraints.
Solutions
Solution
class Solution {public int[][] constructProductMatrix(int[][] grid) { final int mod = 12345; int n = grid.length, m = grid[0].length; int[][] p = new int[n][m]; long suf = 1; for (int i = n - 1; i >= 0; --i) { for (int j = m - 1; j >= 0; --j) { p[i][j] = (int)suf; suf = suf * grid[i][j] % mod; } } long pre = 1; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { p[i][j] = (int)(p[i][j] * pre % mod); pre = pre * grid[i][j] % mod; } } return p; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.