Construct Product Matrix

MEDIUM

Description

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 in grid except for the element grid[i][j]. This product is then taken modulo 12345.

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 <= 10⁵
1 <= m == grid[i].length <= 10⁵
2 <= n * m <= 10⁵
1 <= grid[i][j] <= 10⁹

Approaches

Checkout 2 different approaches to solve Construct Product Matrix. Click on different approaches to view the approach and algorithm in detail.

Brute Force Iteration

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 n and m of the grid.
Create a new result matrix p of size n x m.
Iterate through each cell (i, j) of the grid from (0, 0) to (n-1, m-1).
- Initialize a variable product to 1.
- Iterate through each cell (r, c) of the grid from (0, 0) to (n-1, m-1).
  - If r != i or c != j, then:
    - product = (product * grid[r][c]) % 12345.
- Set p[i][j] = product.
Return p.

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 Analysis

Time Complexity: 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 Complexity: 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`.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Construct Product Matrix. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Construct Product Matrix

Patterns:

Prefix Sum

Data Structures:

ArrayMatrix