Construct Product Matrix

Medium
913.

Construct Product Matrix

Construct Product Matrix is a medium coding problem on arrays, matrix and prefix sum, asked in Amazon, Google and Uber interviews.

Given an m × n grid, build the product matrix p, where p[i][j] is the product of all elements of grid except grid[i][j], taken modulo 12345.

Example 1

Input
grid = [[1,2],[3,4]]
Output
[[24,12],[8,6]]
Explanation
`p[0][0] = 2 · 3 · 4 = 24`.

Example 2

Input
grid = [[12345],[2],[1]]
Output
[[2],[0],[0]]
Explanation
`12345 % 12345` is 0, so every cell but the first becomes 0.

Example 3

Input
grid = [[1,1,1]]
Output
[[1,1,1]]

Constraints

  • m == grid.length
  • n == grid[i].length
  • 2 <= m * n <= 10^5
  • 1 <= grid[i][j] <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @return {number[][]}
 */
var constructProductMatrix = function(grid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Construct Product Matrix — Solution in Python, Java & C++

Construct Product Matrix solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Construct Product Matrix is a medium coding problem on arrays, matrix and prefix sum, asked in Amazon, Google and Uber interviews.

  • Difficulty: Medium
  • Topics: Arrays, Matrix, Prefix Sum
  • Asked at: Amazon, Google, Uber
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given an m × n grid, build the product matrix p, where p[i][j] is the product of all elements of grid except grid[i][j], taken modulo 12345.

Example 1

Input: grid = [[1,2],[3,4]]
Output: [[24,12],[8,6]]
Explanation: `p[0][0] = 2 · 3 · 4 = 24`.

Example 2

Input: grid = [[12345],[2],[1]]
Output: [[2],[0],[0]]
Explanation: `12345 % 12345` is 0, so every cell but the first becomes 0.

Example 3

Input: grid = [[1,1,1]]
Output: [[1,1,1]]

Constraints

  • m == grid.length
  • n == grid[i].length
  • 2 <= m * n <= 10^5
  • 1 <= grid[i][j] <= 10^9

Hints for Construct Product Matrix

  1. Hint 1

    Division is not available: 12345 is not prime, so many elements have no modular inverse.

  2. Hint 2

    Flatten the grid and think about products of prefixes and suffixes.

  3. Hint 3

    p[k] = prefix[k] · suffix[k + 1].

How to solve Construct Product Matrix

Read the grid as one flat sequence. The product of everything except position k is the product of everything before it times the product of everything after it — two running products, no division.

Approach

  1. Compute pre[k] = product of the first k elements, mod 12345.
  2. Sweep from the end keeping suf = product of everything after the current position.
  3. Set p[k] = pre[k] · suf, then fold the current element into suf.
  4. Reshape the flat answers back into m × n.

Why it works

The obvious trick — divide the total product by grid[i][j] — fails because 12345 = 3 · 5 · 823 is composite, so an element sharing a factor with it has no inverse and a zero total product destroys the information. Prefix-suffix products avoid inverses entirely, which is the whole point of the problem.

Complexity

  • Time — O(m · n)
  • Space — O(m · n)

Pitfalls

  • Dividing by the element is wrong under a composite modulus.
  • Reduce each element mod 12345 before multiplying, or the intermediate exceeds 32 bits.
  • The suffix must exclude the current element, so fold it in after writing the answer.

Reference solution

Python

from typing import List

def constructProductMatrix(grid: List[List[int]]) -> List[List[int]]:
    MOD = 12345
    m, n = len(grid), len(grid[0])
    flat = [grid[i][j] % MOD for i in range(m) for j in range(n)]
    total = m * n
    pre = [1] * (total + 1)
    for k in range(total):
        pre[k + 1] = pre[k] * flat[k] % MOD
    val = [0] * total
    suf = 1
    for k in range(total - 1, -1, -1):
        val[k] = pre[k] * suf % MOD
        suf = suf * flat[k] % MOD
    return [val[i * n:(i + 1) * n] for i in range(m)]

Java

public static int[][] constructProductMatrix(int[][] grid) {
    final int MOD = 12345;
    int m = grid.length, n = grid[0].length;
    int total = m * n;
    int[] flat = new int[total];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) flat[i * n + j] = grid[i][j] % MOD;
    }
    int[] pre = new int[total + 1];
    pre[0] = 1;
    for (int k = 0; k < total; k++) pre[k + 1] = (int) ((long) pre[k] * flat[k] % MOD);
    int[] val = new int[total];
    long suf = 1;
    for (int k = total - 1; k >= 0; k--) {
        val[k] = (int) (pre[k] * suf % MOD);
        suf = suf * flat[k] % MOD;
    }
    int[][] out = new int[m][n];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) out[i][j] = val[i * n + j];
    }
    return out;
}

C++

vector<vector<int>> constructProductMatrix(vector<vector<int>>& grid) {
    const long long MOD = 12345;
    int m = (int) grid.size(), n = (int) grid[0].size();
    int total = m * n;
    vector<long long> flat(total);
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) flat[i * n + j] = grid[i][j] % MOD;
    }
    vector<long long> pre(total + 1, 1);
    for (int k = 0; k < total; k++) pre[k + 1] = pre[k] * flat[k] % MOD;
    vector<vector<int>> out(m, vector<int>(n, 0));
    long long suf = 1;
    for (int k = total - 1; k >= 0; k--) {
        out[k / n][k % n] = (int) (pre[k] * suf % MOD);
        suf = suf * flat[k] % MOD;
    }
    return out;
}

JavaScript

var constructProductMatrix = function(grid) {
    var MOD = 12345;
    var m = grid.length, n = grid[0].length, i, j, k;
    var total = m * n;
    var flat = [];
    for (i = 0; i < m; i++) {
        for (j = 0; j < n; j++) flat.push(grid[i][j] % MOD);
    }
    var pre = [1];
    for (k = 0; k < total; k++) pre.push((pre[k] * flat[k]) % MOD);
    var val = new Array(total);
    var suf = 1;
    for (k = total - 1; k >= 0; k--) {
        val[k] = (pre[k] * suf) % MOD;
        suf = (suf * flat[k]) % MOD;
    }
    var out = [];
    for (i = 0; i < m; i++) out.push(val.slice(i * n, i * n + n));
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Matrix and Grid Traversal