LeetCode daily problem P2906 Construct Product Matrix

---

Timeline

Timeline

2026-03-24

init

Prefix sum

---

Problem:

P2906 Construct Product Matrix

https://leetcode.cn/problems/construct-product-matrix/description/?envType=daily-question&envId=2026-03-24

A prefix sum problem in disguise; note that multiplication may exceed the maximum value representable by int.

#include <vector>
using std::vector;

#define MODULO_NUM 12345

class Solution {
    public:
        vector<vector<int> > constructProductMatrix(vector<vector<int> > &grid)
        {
                // 1 <= n == grid.length <= 105
                // 1 <= m == grid[i].length <= 105
                // 2 <= n * m <= 105
                // 1 <= grid[i][j] <= 109
                int i, j, m = grid.size(), n = grid[0].size();
                int total = m * n, last;
                vector<vector<int> > product_matrix(m, (vector<int>(n, 0)));
                vector<int> prefix_product(total, 1);
                vector<int> suffix_product(total, 1);

                // prefix
                last = grid[0][0];
                for (i = 0; i < m; i++) {
                        for (j = 0; j < n; j++) {
                                if (i == 0 && j == 0)
                                        continue;

                                prefix_product[i * n + j] =
                                        (long)((long)last * (long)prefix_product[i * n + j - 1]) %
                                        MODULO_NUM;
                                last = grid[i][j];
                        }
                }
                // suffix
                last = grid[m - 1][n - 1];
                for (i = m - 1; i >= 0; i--) {
                        for (j = n - 1; j >= 0; j--) {
                                if (i == m - 1 && j == n - 1)
                                        continue;
                                suffix_product[i * n + j] =
                                        (long)((long)last * (long)suffix_product[i * n + j + 1]) %
                                        MODULO_NUM;
                                last = grid[i][j];
                        }
                }

                for (i = 0; i < m; i++) {
                        for (j = 0; j < n; j++) {
                                product_matrix[i][j] = (long)((long)prefix_product[i * n + j] *
                                                              (long)suffix_product[i * n + j]) %
                                                       MODULO_NUM;
                        }
                }

                return product_matrix;
        }
};