# Construct Product Matrix
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/construct-product-matrix)
Canonical: https://scaleengineer.com/dsa/problems/construct-product-matrix
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array, Matrix
---
## Problem
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 <= 105`
* `1 <= m == grid[i].length <= 105`
* `2 <= n * m <= 105`
* `1 <= grid[i][j] <= 109`

# Approaches
## 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]`.
**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`.
**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.
### Explanation
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)`.

```java
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;
    }
}
```
### 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`.

## Two-Pass Prefix and Suffix Product
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.
**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.
**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.
### Explanation
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]`.

```java
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;
    }
}
```
### Algorithm
- Get dimensions `n`, `m`. Let `mod = 12345`.
- Create result matrix `p` of size `n 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`.
- **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`.
- Return `p`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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 p

```