Problem Description

You are given a 2D integer matrix grid of size n × m (0-indexed). Your task is to create a new matrix p of the same size where each element p[i][j] equals the product of all elements in grid except grid[i][j] itself, with the result taken modulo 12345.

In other words, for each position (i, j) in the result matrix:

• Calculate the product of all elements in the entire grid matrix
• Exclude only the element at position grid[i][j] from this product
• Take the result modulo 12345
• Store this value at p[i][j]

For example, if you have a 2×2 grid:

grid = [[1, 2],
        [3, 4]]

Then p[0][0] would be (2 × 3 × 4) % 12345 = 24, because we multiply all elements except grid[0][0] which is 1.

The challenge is to efficiently compute this for every position in the matrix and return the resulting product matrix p.

Intuition

The naive approach would be to calculate the product of all elements except grid[i][j] for each position, but this would involve repeated multiplication of the same elements, leading to inefficient O(n²m²) time complexity.

The key insight is that for any position (i, j), the product of all other elements can be broken down into two parts:

1. The product of all elements that come "before" position (i, j)
2. The product of all elements that come "after" position (i, j)

This is similar to the classic "Product of Array Except Self" problem, but extended to 2D. We can think of the 2D matrix as a flattened 1D array where we traverse row by row.

For each element, if we know:

• The product of all elements before it (prefix product)
• The product of all elements after it (suffix product)

Then the answer for that position is simply prefix × suffix.

To implement this efficiently, we can make two passes through the matrix:

First Pass (Backward): Start from the bottom-right corner and move towards the top-left. For each position, we store the product of all elements that come after it in the traversal order. This gives us the suffix product for each position.

Second Pass (Forward): Start from the top-left corner and move towards the bottom-right. For each position, we multiply the previously calculated suffix product by the running prefix product (product of all elements before the current position).

This way, each element is visited exactly twice, giving us O(nm) time complexity instead of O(n²m²). The modulo operation is applied at each step to prevent overflow and meet the problem requirements.

Learn more about Prefix Sum patterns.

Solution Approach

The solution uses prefix and suffix decomposition to efficiently calculate the product matrix. Here's how the implementation works:

Step 1: Initialize the Result Matrix

n, m = len(grid), len(grid[0])
p = [[0] * m for _ in range(n)]
mod = 12345

We create a result matrix p with the same dimensions as grid and define the modulo value.

Step 2: Calculate Suffix Products (Backward Pass)

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

• Start from the bottom-right corner (n-1, m-1) and traverse backwards
• For each position (i, j), store the current suf value in p[i][j]
• Update suf by multiplying it with grid[i][j] and taking modulo
• At each position, p[i][j] now contains the product of all elements that come after it in row-major order

Step 3: Calculate Prefix Products and Combine (Forward Pass)

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

• Start from the top-left corner (0, 0) and traverse forward
• For each position (i, j), multiply the stored suffix product p[i][j] with the current prefix product pre
• Update pre by multiplying it with grid[i][j] and taking modulo
• After this step, p[i][j] contains (prefix product) × (suffix product), which equals the product of all elements except grid[i][j]

Why This Works:

• After the backward pass, p[i][j] contains the product of all elements that come after position (i, j)
• During the forward pass, pre contains the product of all elements that come before position (i, j)
• Multiplying these two values gives us the product of all elements except grid[i][j]
• The modulo operation at each step ensures the values stay within bounds

Time Complexity: O(n × m) - we traverse the matrix twice Space Complexity: O(n × m) - for storing the result matrix

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Consider a 2×3 grid:

grid = [[2, 3, 4],
        [5, 6, 7]]

We want to create matrix p where each p[i][j] is the product of all elements except grid[i][j], modulo 12345.

Step 1: Initialize

• Create result matrix p with same dimensions (2×3)
• Set mod = 12345

Step 2: Backward Pass (Calculate Suffix Products)

We traverse from bottom-right to top-left, maintaining suf (suffix product):

Starting with suf = 1:

• Position (1,2): p[1][2] = 1, then suf = 1 × 7 = 7
• Position (1,1): p[1][1] = 7, then suf = 7 × 6 = 42
• Position (1,0): p[1][0] = 42, then suf = 42 × 5 = 210
• Position (0,2): p[0][2] = 210, then suf = 210 × 4 = 840
• Position (0,1): p[0][1] = 840, then suf = 840 × 3 = 2520
• Position (0,0): p[0][0] = 2520, then suf = 2520 × 2 = 5040

After backward pass:

p = [[2520, 840, 210],
     [42,   7,   1]]

Each cell contains the product of all elements that come after it in row-major order.

Step 3: Forward Pass (Calculate Prefix Products and Combine)

We traverse from top-left to bottom-right, maintaining pre (prefix product):

Starting with pre = 1:

• Position (0,0): p[0][0] = 2520 × 1 = 2520, then pre = 1 × 2 = 2
• Position (0,1): p[0][1] = 840 × 2 = 1680, then pre = 2 × 3 = 6
• Position (0,2): p[0][2] = 210 × 6 = 1260, then pre = 6 × 4 = 24
• Position (1,0): p[1][0] = 42 × 24 = 1008, then pre = 24 × 5 = 120
• Position (1,1): p[1][1] = 7 × 120 = 840, then pre = 120 × 6 = 720
• Position (1,2): p[1][2] = 1 × 720 = 720, then pre = 720 × 7 = 5040

Final result:

p = [[2520, 1680, 1260],
     [1008, 840,  720]]

Verification: Let's verify p[0][1] = 1680:

• Product of all elements except grid[0][1] (which is 3)
• = 2 × 4 × 5 × 6 × 7 = 1680 ✓

And p[1][1] = 840:

• Product of all elements except grid[1][1] (which is 6)
• = 2 × 3 × 4 × 5 × 7 = 840 ✓

The algorithm correctly computes the product of all elements except the current one for each position, using only two passes through the matrix.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × m)

The algorithm traverses the entire grid twice:

• First traversal: iterates through all elements from bottom-right to top-left to calculate suffix products, which takes O(n × m) time
• Second traversal: iterates through all elements from top-left to bottom-right to combine prefix products with the previously calculated suffix products, which takes O(n × m) time

Total time complexity: O(n × m) + O(n × m) = O(n × m), where n is the number of rows and m is the number of columns in the grid.

Space Complexity: O(1) (excluding the output matrix)

The algorithm uses:

• The output matrix p of size n × m, which is required for the result and typically not counted in space complexity analysis
• Three variables: suf, pre, and mod, which use constant space O(1)
• Variables i, j, n, and m for loop control and dimensions, which use constant space O(1)

If we include the output matrix in the space complexity analysis, it would be O(n × m). However, following the convention stated in the reference answer where the space occupied by the result matrix is ignored, the space complexity is O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Overflow During Multiplication

One of the most common pitfalls in this problem is not handling the modulo operation correctly, which can lead to integer overflow even before applying the modulo.

Incorrect approach:

# Wrong - can cause overflow
suffix_product = suffix_product * grid[row][col]
suffix_product = suffix_product % MOD

Correct approach:

# Right - apply modulo immediately
suffix_product = (suffix_product * grid[row][col]) % MOD

2. Handling Zero Elements

When the grid contains zeros, the product calculation needs special attention. If there's exactly one zero, only that position should have a non-zero value in the result. If there are multiple zeros, all positions should be zero.

Solution:

def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:
    rows, cols = len(grid), len(grid[0])
    result = [[0] * cols for _ in range(rows)]
    MOD = 12345
  
    # Count zeros and track their position
    zero_count = 0
    zero_pos = None
    total_product = 1
  
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == 0:
                zero_count += 1
                zero_pos = (i, j)
            else:
                total_product = (total_product * grid[i][j]) % MOD
  
    # If more than one zero, all results are zero
    if zero_count > 1:
        return result
  
    # If exactly one zero, only that position has non-zero value
    if zero_count == 1:
        result[zero_pos[0]][zero_pos[1]] = total_product
        return result
  
    # Original algorithm for no zeros
    # ... (continue with prefix-suffix approach)

3. Row-Major Order Traversal Confusion

The algorithm assumes row-major order traversal (left-to-right, top-to-bottom). Mixing up the traversal order or indices can lead to incorrect results.

Common mistake:

# Wrong - column-major traversal in suffix pass
for j in range(cols - 1, -1, -1):
    for i in range(rows - 1, -1, -1):
        result[i][j] = suffix_product
        suffix_product = (suffix_product * grid[i][j]) % MOD

Correct approach:

# Right - row-major traversal
for i in range(rows - 1, -1, -1):
    for j in range(cols - 1, -1, -1):
        result[i][j] = suffix_product
        suffix_product = (suffix_product * grid[i][j]) % MOD

4. Modulo Properties with Division

If attempting an alternative approach using total product divided by current element, remember that modular division requires the modular multiplicative inverse, which doesn't always exist.

Problematic approach:

# Wrong - division doesn't work directly with modulo
total_product = calculate_total_product(grid) % MOD
for i in range(rows):
    for j in range(cols):
        result[i][j] = (total_product // grid[i][j]) % MOD  # Incorrect!

The prefix-suffix approach avoids this issue entirely by never requiring division.