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 Evaluator

Example Walkthrough

Let's walk through the solution with a small example. Consider the following grid matrix of size 3x3:

1grid = [
2  [1, 2, 3],
3  [4, 5, 6],
4  [7, 8, 9]
5]

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:

1Iteration 1: (i=2, j=2) => p[2][2] = suf (1) => p = [
2  [?, ?, ?],
3  [?, ?, ?],
4  [?, ?, 1]
5]
6suf = 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:

1p = [
2  [1, 1, 1],
3  [1, 1, 2],
4  [1, 9, 1]
5]

Step 2: Initialize pre to 1 and traverse the matrix in normal order:

1Iteration 1: (i=0, j=0) => p[0][0] = suf * pre % 12345 => p[0][0] = 1 * 1 % 12345 = 1
2pre = 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:

1p = [
2  [(5*6*7*8*9) % 12345, (4*6*7*8*9) % 12345, (4*5*7*8*9) % 12345],
3  [(2*3*7*8*9) % 12345, (1*3*7*8*9) % 12345, (1*2*7*8*9) % 12345],
4  [(2*3*5*6) % 12345, (1*3*5*6) % 12345, (1*2*5*6) % 12345]
5]

With some arithmetic, we find:

1p = [
2  [15120 % 12345, 60480 % 12345, 30240 % 12345],
3  [60480 % 12345, 30240 % 12345, 40320 % 12345],
4  [360 % 12345, 180 % 12345, 60 % 12345]
5]

And, finally, the resulting p matrix is:

1p = [
2  [2775, 10530, 7895],
3  [10530, 7895, 10080],
4  [360, 180, 60]
5]

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.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which of the following uses divide and conquer strategy?


Recommended Readings

Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns
←
↑đŸȘ„