2906. Construct Product Matrix
Problem Description
This problem provides a matrix grid
of size n * m
and requires us to construct a new matrix p
, also of size n * m
. The new matrix p
is defined as the product matrix of grid
, where each element p[i][j]
is the product of all elements in grid
excluding the element grid[i][j]
, with each product taken modulo 12345
.
To elaborate, if we were to calculate p[i][j]
, we would take the product of all the numbers in the matrix grid
except for grid[i][j]
, and then take the result modulo 12345
. Our task is to construct the entire matrix p
that satisfies this condition for every single element.
Intuition
Constructing the product matrix p
can appear challenging at first because of the requirement to exclude the current element from the product. A naive approach might involve calculating the product of all elements for each position separately, which would lead to a time-consuming process because of the repeated multiplications. However, this problem can be efficiently solved by decomposing the operations into prefix and suffix products. This approach allows us to calculate the desired product for each element without redundancy.
The intuition for the solution is to first calculate the suffix product matrix, which stores the product of all elements that are below and to the right of the current position. This is done by traversing the matrix from the bottom right corner upwards. Following this, we can calculate the prefix product for each element by traversing the matrix from the top left corner downwards, multiplying the already calculated suffix product by the prefix and taking the modulo at each step. By doing these two separate traversals, we cleverly circumvent the need to directly exclude the current element (since it was never included in suf
or pre
, to begin with).
Ultimately, the p[i][j]
equals to the multiplication of the suffix product (calculated in the first traversal) and the prefix product (calculated in the second traversal). Both of these are calculated modulo 12345
as per the problem statement. As we are making use of previously computed results, computational efficiency is greatly improved over the naive approach.
Learn more about Prefix Sum patterns.
Solution Approach
The problem dictates a classic use of Algorithmic Patterns in which the prefix and suffix multiplications are used to simplify the process of excluding a particular element from the product. The solution employs two important concepts: suffix and prefix product decomposition. To implement the solution, we initialize a product matrix p
and two variables, suf
and pre
, which will hold the suffix and prefix products, respectively.
Step 1: Initialize the suf
variable (suffix product
) to 1. Here, suf
acts as a running product of all elements to the right and below the current element, excluding it. Starting from the bottom right corner of the matrix, iterate over the matrix in reverse order. For each element grid[i][j]
, we will set p[i][j]
to the current suf
value. Then, we update the suf
by multiplying it by the current element in grid
and taking the modulo 12345
as prescribed by the problem.
Step 2: The next traversal calculates the prefix product. Initialize the pre
variable (prefix product
) to 1. Starting from the top left corner of the matrix, iterate over the matrix in normal order. For each element grid[i][j]
, we multiply the p[i][j]
(which at this moment only contains the suffix product) by the current pre
, take the modulo 12345
, and then update the pre
with the current element in grid
, also with a modulo operation.
The processes indicated in Step 1 and Step 2 ensure that each p[i][j]
is calculated by multiplying the prefix product. Up to but not including grid[i][j]
, with the suffix product of all elements after grid[i][j]
, effectively excluding grid[i][j]
from the product as required.
The reason we can do this in two separate steps is because of the mathematical property that allows us to separate the product of a series of numbers into separate parts, compute them independently, and then combine them to get the final product. This separation into prefix and suffix helps us avoid including the current element in either product. The modulo operation is an integral part of every product calculation due to the requirement to take each product modulo 12345
.
By employing this specific order of operationāsuffix product calculation followed by prefix product multiplicationāwe avoid the use of division, which is beneficial when dealing with modulus operations as division is not well-defined under modulus without additional steps (like using a multiplicative inverse). Therefore, this technique not only meets the problem constraints but also adheres to the computational limitations when dealing with modular arithmetic.
Finally, after the completion of these two passes, the matrix p
is returned, containing the desired product matrix. This approach efficiently computes the solution in O(nxm)
time complexity with O(nxm)
space complexity, where n
and m
are the dimensions of the input matrix grid
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through the solution with a small example. Consider the following grid
matrix of size 3x3
:
grid = [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ]
To construct the new matrix p
, we will follow the solution approach detailed in the content.
Step 1: Initialize suf
to 1 and traverse the matrix in reverse order. Let's start at the bottom-right corner:
Iteration 1: (i=2, j=2) => p[2][2] = suf (1) => p = [ [?, ?, ?], [?, ?, ?], [?, ?, 1] ] suf = suf * grid[2][2] % 12345 => suf = 1 * 9 % 12345 = 9
(This process repeats for the remaining elements of the matrix from the bottom-right to the top-left.)
After the first traversal, the p
matrix will have the suffix products:
p = [ [1, 1, 1], [1, 1, 2], [1, 9, 1] ]
Step 2: Initialize pre
to 1 and traverse the matrix in normal order:
Iteration 1: (i=0, j=0) => p[0][0] = suf * pre % 12345 => p[0][0] = 1 * 1 % 12345 = 1 pre = pre * grid[0][0] % 12345 => pre = 1 * 1 % 12345 = 1
(In a similar fashion, we update each element in p
for the whole matrix in normal order.)
After the second traversal, we fully calculate the p
matrix:
p = [ [(5*6*7*8*9) % 12345, (4*6*7*8*9) % 12345, (4*5*7*8*9) % 12345], [(2*3*7*8*9) % 12345, (1*3*7*8*9) % 12345, (1*2*7*8*9) % 12345], [(2*3*5*6) % 12345, (1*3*5*6) % 12345, (1*2*5*6) % 12345] ]
With some arithmetic, we find:
p = [ [15120 % 12345, 60480 % 12345, 30240 % 12345], [60480 % 12345, 30240 % 12345, 40320 % 12345], [360 % 12345, 180 % 12345, 60 % 12345] ]
And, finally, the resulting p matrix is:
p = [ [2775, 10530, 7895], [10530, 7895, 10080], [360, 180, 60] ]
The new p
matrix is the product matrix of grid
, where each entry is the product of all other elements except itself, modulo 12345
. Thus, by using the suffix and prefix product computation, we've successfully found the solution without directly excluding each grid[i][j]
from the multiplication, proving the efficiency of this approach.
Solution Implementation
1class Solution:
2 def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:
3 # Determine the number of rows and columns in the given grid
4 num_rows, num_cols = len(grid), len(grid[0])
5
6 # Initialize a product matrix with zeros, of the same dimensions as the grid
7 product_matrix = [[0] * num_cols for _ in range(num_rows)]
8
9 # Define the modulo value as stated in the problem
10 modulo = 12345
11
12 # Initialize the suffix product variable
13 suffix_product = 1
14
15 # Calculate suffix products (right to left, bottom to top)
16 for row in range(num_rows - 1, -1, -1):
17 for col in range(num_cols - 1, -1, -1):
18 # Store the current suffix product in the product_matrix at [row][col]
19 product_matrix[row][col] = suffix_product
20 # Update the suffix product (include the current grid value)
21 suffix_product = suffix_product * grid[row][col] % modulo
22
23 # Initialize the prefix product variable
24 prefix_product = 1
25
26 # Calculate the final product matrix values using prefix products
27 for row in range(num_rows):
28 for col in range(num_cols):
29 # Multiply the prefix product with the already stored suffix product and apply modulo
30 product_matrix[row][col] = product_matrix[row][col] * prefix_product % modulo
31 # Update the prefix product (include the current grid value)
32 prefix_product = prefix_product * grid[row][col] % modulo
33
34 # Return the final product matrix
35 return product_matrix
36
37# Example usage:
38# solution = Solution()
39# matrix = solution.constructProductMatrix([[1, 2], [3, 4]])
40# print(matrix)
41
1class Solution {
2 public int[][] constructProductMatrix(int[][] grid) {
3 final int MOD = 12345; // Constant representing the modulo value
4 int rows = grid.length;
5 int cols = grid[0].length;
6 int[][] productMatrix = new int[rows][cols]; // Initialize product matrix
7 long suffixProduct = 1; // Used for suffix product calculation
8
9 // Calculate suffix products for each element and store them in the product matrix
10 for (int i = rows - 1; i >= 0; --i) {
11 for (int j = cols - 1; j >= 0; --j) {
12 productMatrix[i][j] = (int) suffixProduct; // Cast long to int
13 suffixProduct = suffixProduct * grid[i][j] % MOD; // Modulo to prevent overflow
14 }
15 }
16
17 long prefixProduct = 1; // Used for prefix product calculation
18
19 // Calculate prefix product and multiply with the corresponding suffix products
20 for (int i = 0; i < rows; ++i) {
21 for (int j = 0; j < cols; ++j) {
22 productMatrix[i][j] = (int) (productMatrix[i][j] * prefixProduct % MOD); // Final product with modulo
23 prefixProduct = prefixProduct * grid[i][j] % MOD; // Update prefix product
24 }
25 }
26
27 return productMatrix; // Return the constructed product matrix
28 }
29}
30
1#include <vector>
2
3class Solution {
4public:
5 // Function to construct a product matrix based on the input grid.
6 // Each element in the product matrix will contain the product of all
7 // elements in the input grid, modulo a predefined value.
8 std::vector<std::vector<int>> constructProductMatrix(std::vector<std::vector<int>>& grid) {
9 // The modulo constant as specified.
10 const int MODULO = 12345;
11
12 // Get the dimensions of the grid.
13 int rowCount = grid.size();
14 int colCount = grid[0].size();
15
16 // Initialize the product matrix with the same dimensions as the input grid.
17 std::vector<std::vector<int>> productMatrix(rowCount, std::vector<int>(colCount));
18
19 // This variable will hold the suffix product as we traverse the matrix
20 // from bottom-right to top-left.
21 long long suffixProduct = 1;
22
23 // Compute the suffix product for each element in the grid.
24 for (int row = rowCount - 1; row >= 0; --row) {
25 for (int col = colCount - 1; col >= 0; --col) {
26 productMatrix[row][col] = suffixProduct;
27 suffixProduct = suffixProduct * grid[row][col] % MODULO;
28 }
29 }
30
31 // This variable will hold the prefix product as we traverse the matrix
32 // from top-left to bottom-right.
33 long long prefixProduct = 1;
34
35 // Compute the prefix product for each element in the grid and multiply
36 // it with the corresponding suffix product.
37 // Finally, take the modulo of the product to fit the result within the specified range.
38 for (int row = 0; row < rowCount; ++row) {
39 for (int col = 0; col < colCount; ++col) {
40 productMatrix[row][col] = productMatrix[row][col] * prefixProduct % MODULO;
41 prefixProduct = prefixProduct * grid[row][col] % MODULO;
42 }
43 }
44
45 // Return the resulting product matrix.
46 return productMatrix;
47 }
48};
49
1/**
2 * Creates a product matrix from the given grid where each element is the product of all other elements in the grid excluding the current element, modulo `mod`.
3 * @param {number[][]} grid - The input grid of numbers.
4 * @returns {number[][]} - The product matrix.
5 */
6function constructProductMatrix(grid: number[][]): number[][] {
7 // Define a modulo constant.
8 const mod = 12345;
9 // Extract grid dimensions.
10 const numRows = grid.length;
11 const numCols = grid[0].length;
12 // Initialize the product matrix with zeroes.
13 const productMatrix: number[][] = Array.from({ length: numRows }, () => Array(numCols).fill(0));
14 // Variable to track suffix product.
15 let suffixProduct = 1;
16
17 // Compute the product of elements to the right and below the current element.
18 for (let row = numRows - 1; row >= 0; row--) {
19 for (let col = numCols - 1; col >= 0; col--) {
20 productMatrix[row][col] = suffixProduct;
21 suffixProduct = (suffixProduct * grid[row][col]) % mod;
22 }
23 // Reset the suffix product for the next row.
24 suffixProduct = 1;
25 }
26
27 // Variable to track prefix product.
28 let prefixProduct = 1;
29
30 // Multiply the prefix product to the existing product in productMatrix and
31 // Compute the product of elements to the left and above the current element.
32 for (let row = 0; row < numRows; row++) {
33 for (let col = 0; col < numCols; col++) {
34 productMatrix[row][col] = (productMatrix[row][col] * prefixProduct) % mod;
35 prefixProduct = (prefixProduct * grid[row][col]) % mod;
36 }
37 // Reset the prefix product for the next row.
38 prefixProduct = 1;
39 }
40
41 // Return the completed product matrix.
42 return productMatrix;
43}
44
Time and Space Complexity
The time complexity of the provided code is O(n * m)
, where n
is the number of rows and m
is the number of columns in the input grid
. This complexity arises because the code contains two nested loops, each of which iterates over every cell in the matrix exactly once.
As for the space complexity, aside from the space needed for the output matrix p
, the space complexity is O(1)
. This is because there are only a finite number of additional variables (n
, m
, suf
, pre
, and mod
) that do not depend on the size of the input matrix, therefore occupying constant space.
Learn more about how to find time and space complexity quickly using problem constraints.
What data structure does Breadth-first search typically uses to store intermediate states?
Recommended Readings
Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!