Leetcode 2906: Construct Product Matrix
You are given a 2D integer matrix grid of size n * m. Your task is to calculate a new 2D matrix p of the same size, where each element p[i][j] is the product of all elements in grid except for grid[i][j]. The result for each element should be taken modulo 12345.
Problem
Approach
Steps
Complexity
Input: The input consists of a 2D matrix grid with dimensions n * m, where each element grid[i][j] is an integer.
Example: grid = [[2, 3], [4, 5]]
Constraints:
• 1 <= n == grid.length <= 10^5
• 1 <= m == grid[i].length <= 10^5
• 2 <= n * m <= 10^5
• 1 <= grid[i][j] <= 10^9
Output: Return a 2D matrix where each element p[i][j] is the product of all other elements in grid[i][j], modulo 12345.
Example: For input grid = [[2, 3], [4, 5]], the output is [[20, 15], [12, 10]].
Constraints:
• The output matrix must have the same dimensions as the input grid.
Goal: The goal is to compute the product for each element in the matrix, excluding the element itself, and take the result modulo 12345.
Steps:
• Initialize two matrices xx and yy. Iterate over the grid to fill xx with products of elements from top-left to bottom-right, and yy with products from bottom-right to top-left.
• For each element p[i][j], calculate its value by multiplying the corresponding values from xx and yy, modulo 12345.
Goal: The input matrix can be large, so ensure the solution is efficient.
Steps:
• 1 <= n * m <= 10^5
• The elements in the grid are integers between 1 and 10^9.
Assumptions:
• Matrix dimensions are reasonable, meaning n * m <= 10^5.
• Elements in the matrix are positive integers.
• Input: grid = [[12345], [2], [1]]
• Explanation: For each element, calculate the product of all elements except for the current one, taking care to compute modulo 12345.
Approach: The approach involves calculating two matrices, one storing products from the top-left to bottom-right and the other from bottom-right to top-left. The final product matrix is derived by multiplying corresponding values from these two matrices.
Observations:
• The challenge is to handle large input sizes efficiently.
• By calculating the products from different directions, we can avoid recalculating the product for each element multiple times.
Steps:
• Initialize two matrices, xx and yy.
• Fill xx by multiplying elements from left to right.
• Fill yy by multiplying elements from right to left.
• Compute the final product matrix by multiplying the corresponding elements from xx and yy.
Empty Inputs:
• Handle the case where n or m is 0, though it is not required by the constraints.
Large Inputs:
• Optimize for large grid sizes (n * m up to 10^5).
Special Values:
• Take care with elements that are equal to 12345, since they can affect modulo operations.
Constraints:
• Ensure the solution handles the constraints efficiently.
vector<vector<int>> constructProductMatrix(vector<vector<int>>& grid) {
int n = grid.size();
int m = grid[0].size();
vector<vector<int>>ans(n,vector<int>(m));
vector<vector<int>>xx(n,vector<int>(m));
vector<vector<int>>yy(n,vector<int>(m));
int mod = 12345;
long long p = 1;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
xx[i][j] = p;
p *= grid[i][j];
p %= mod;
}
}
p = 1;
for(int i=n-1; i>=0; i--){
for(int j=m-1; j>=0; j--){
yy[i][j] = p;
p *= grid[i][j];
p %= mod;
}
}
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
long long mul = xx[i][j] * yy[i][j];
ans[i][j] = mul%mod;
}
}
return ans;
}
1 : Function Definition
vector<vector<int>> constructProductMatrix(vector<vector<int>>& grid) {
Defines the function `constructProductMatrix` which takes a 2D vector `grid` and returns a 2D vector where each element is the product of grid values from the top-left to the current cell and from the bottom-right to the current cell.
2 : Size Initialization
int n = grid.size();
Initializes `n` with the number of rows in the `grid`.
3 : Size Initialization
int m = grid[0].size();
Initializes `m` with the number of columns in the first row of `grid`.
4 : Matrix Initialization
vector<vector<int>>ans(n,vector<int>(m));
Initializes a 2D vector `ans` to store the final result of the product matrix, with the same dimensions as the input `grid`.
5 : Matrix Initialization
vector<vector<int>>xx(n,vector<int>(m));
Initializes a 2D vector `xx` to store products of elements from the top-left of the grid to each element.
6 : Matrix Initialization
vector<vector<int>>yy(n,vector<int>(m));
Initializes a 2D vector `yy` to store products of elements from the bottom-right of the grid to each element.
7 : Modulo Initialization
int mod = 12345;
Sets a constant modulo value `mod` used to compute the remainder of the product for each element in the matrix.
8 : Variable Initialization
long long p = 1;
Initializes a variable `p` to store the running product while iterating through the grid.
9 : Forward Iteration
for(int i=0; i<n; i++){
Begins a loop to iterate through the rows of the grid.
10 : Forward Iteration Inner Loop
for(int j=0; j<m; j++){
Begins an inner loop to iterate through the columns of the grid.
11 : Storing Products in xx
xx[i][j] = p;
Stores the current running product `p` in the `xx` matrix at position `(i, j)`.
12 : Product Calculation
p *= grid[i][j];
Multiplies the running product `p` by the current element `grid[i][j]`.
13 : Modulo Operation
p %= mod;
Applies the modulo operation to `p` to ensure the product remains within a manageable range.
14 : Resetting p
p = 1;
Resets the variable `p` to `1` before starting the backward iteration.
15 : Backward Iteration
for(int i=n-1; i>=0; i--){
Begins a loop to iterate through the rows of the grid in reverse order.
16 : Backward Iteration Inner Loop
for(int j=m-1; j>=0; j--){
Begins an inner loop to iterate through the columns in reverse order.
17 : Storing Products in yy
yy[i][j] = p;
Stores the current running product `p` in the `yy` matrix at position `(i, j)`.
18 : Product Calculation
p *= grid[i][j];
Multiplies the running product `p` by the current element `grid[i][j]`.
19 : Modulo Operation
p %= mod;
Applies the modulo operation to `p` to ensure the product remains within a manageable range.
20 : Final Computation
for(int i=0; i<n; i++){
Begins a loop to iterate through all the rows for the final computation of the product matrix.
21 : Final Computation Inner Loop
for(int j=0; j<m; j++){
Begins an inner loop to iterate through the columns for the final computation.
22 : Product Calculation
long long mul = xx[i][j] * yy[i][j];
Calculates the product of the values from `xx[i][j]` and `yy[i][j]`.
23 : Storing Final Result
ans[i][j] = mul%mod;
Stores the final product in `ans[i][j]` after applying the modulo operation.
24 : Return Statement
return ans;
Returns the final product matrix `ans`.
Best Case: O(n * m)
Average Case: O(n * m)
Worst Case: O(n * m)
Description: Since we iterate over the matrix several times, the time complexity is linear in terms of the number of elements.
Best Case: O(n * m)
Worst Case: O(n * m)
Description: The space complexity is linear in terms of the size of the grid, as we use two additional matrices of the same size.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus