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.
This approach is significantly more efficient and is analogous to the classic "Product of Array Except Self" problem. We can treat the 2D grid as a flattened 1D array and make two passes over it. The first pass calculates the product of all elements before the current element (prefix product), and the second pass calculates the product of all elements after the current element (suffix product). The final result for an element is the product of its prefix and suffix products.
Algorithm
- Get dimensions
n,m. Letmod = 12345. - Create result matrix
pof sizen x m. - Pass 1: Prefix Products
- Initialize
prefix_product = 1(as a long to prevent overflow). - Iterate from
(i=0, j=0)to(n-1, m-1):p[i][j] = (int) prefix_product.prefix_product = (prefix_product * grid[i][j]) % mod.
- Initialize
- Pass 2: Suffix Products
- Initialize
suffix_product = 1(as a long). - Iterate from
(i=n-1, j=m-1)down to(0, 0):p[i][j] = (int) (((long)p[i][j] * suffix_product) % mod).suffix_product = (suffix_product * grid[i][j]) % mod.
- Initialize
- Return
p.
Walkthrough
The core idea is to avoid redundant calculations. For any element grid[i][j], the desired product is (product of all elements before it) * (product of all elements after it). We can compute these prefix and suffix products efficiently in two separate passes.
Pass 1 (Prefix Calculation):
We create the result matrix p. We iterate through the grid elements from top-left to bottom-right (as if it were a 1D array). We maintain a prefixProduct variable, initialized to 1. For each cell (i, j), we first set p[i][j] to the current prefixProduct. This prefixProduct represents the product of all elements encountered before (i, j). Then, we update prefixProduct by multiplying it with the current element grid[i][j] (modulo 12345).
Pass 2 (Suffix Calculation):
We iterate through the grid elements in reverse, from bottom-right to top-left. We maintain a suffixProduct variable, also initialized to 1. For each cell (i, j), we multiply its current value p[i][j] (which now holds the prefix product) by the current suffixProduct. This suffixProduct represents the product of all elements encountered after (i, j). Then, we update suffixProduct by multiplying it with the current element grid[i][j] (modulo 12345).
After both passes, p[i][j] will correctly hold the product of all elements except grid[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; // Pass 1: Calculate prefix products long prefixProduct = 1; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { p[i][j] = (int) prefixProduct; prefixProduct = (prefixProduct * grid[i][j]) % mod; } } // Pass 2: Calculate suffix products and final result long suffixProduct = 1; for (int i = n - 1; i >= 0; i--) { for (int j = m - 1; j >= 0; j--) { p[i][j] = (int) ((long) p[i][j] * suffixProduct % mod); suffixProduct = (suffixProduct * grid[i][j]) % mod; } } return p; }}Complexity
Time
O(n*m) or O(N), where N is the total number of elements. We make two linear passes over the grid, which is significantly faster than the brute-force approach.
Space
O(n*m) or O(1) extra space. The space is dominated by the output matrix `p`. If the output matrix is not considered extra space, the algorithm uses O(1) extra space for the `prefixProduct` and `suffixProduct` variables.
Trade-offs
Pros
Highly efficient with a linear time complexity.
Optimal time and space complexity for this problem.
Cons
Slightly more complex to conceptualize than the brute-force approach.
Requires two separate passes over the data.
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; }}class Solution {public: vector<vector<int>> constructProductMatrix(vector<vector<int>> &grid) { const int mod = 12345; int n = grid.size(), m = grid[0].size(); vector<vector<int>> p(n, vector<int>(m)); long long suf = 1; for (int i = n - 1; i >= 0; --i) { for (int j = m - 1; j >= 0; --j) { p[i][j] = suf; suf = suf * grid[i][j] % mod; } } long long pre = 1; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { p[i][j] = p[i][j] * pre % mod; pre = pre * grid[i][j] % mod; } } return p; }};class Solution: def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]: n, m = len(grid), len(grid[0]) p = [[0] * m for _ in range(n)] mod = 12345 suf = 1 for i in range(n - 1, - 1, - 1): for j in range(m - 1, - 1, - 1): p[i][j] = suf suf = suf * grid[i][j] % mod pre = 1 for i in range(n): for j in range(m): p[i][j] = p[i][j] * pre % mod pre = pre * grid[i][j] % mod return pVideo 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.