Construct Product Matrix - Solution & Explanation

Problem Overview: You are given an m x n grid. For every cell (i, j), compute the product of all elements in the matrix except grid[i][j]. Each result must be returned modulo 12345. The challenge is avoiding repeated multiplication across the entire matrix for every cell.

Approach 1: Brute Force Multiplication (O((mn)^2) time, O(1) space)

The most direct approach iterates through the matrix and recomputes the product of all elements except the current one. For each position (i, j), traverse the entire grid again and multiply every value except that cell. Apply modulo 12345 during multiplication to keep numbers small. This approach works but quickly becomes inefficient because each of the mn cells requires scanning the entire matrix again. Time complexity becomes O((mn)^2), which is too slow when the grid contains many elements.

Approach 2: Prefix and Suffix Decomposition (O(mn) time, O(mn) space)

The key insight is identical to the classic "product of array except self" pattern. Flatten the matrix conceptually into a 1D sequence of length mn. Instead of recomputing products repeatedly, build prefix and suffix products. The prefix array stores the product of all elements before index k, while the suffix array stores the product of all elements after k. The result for each position becomes (prefix[k] * suffix[k]) % 12345. Finally map the flattened index back into the array position (i, j).

This works because every element's contribution is captured either in the prefix or suffix side. Multiplication is performed exactly once per element in each pass. The algorithm performs two linear scans across the matrix elements, giving O(mn) time complexity. Extra storage for prefix and suffix products results in O(mn) space, although careful implementation can reduce auxiliary memory. The idea is closely related to prefix computation techniques often used to reuse partial results efficiently.

Recommended for interviews: The prefix and suffix decomposition approach is the expected solution. It demonstrates recognition of the "product except self" pattern and the ability to adapt it to a 2D matrix with modular arithmetic. Mentioning the brute force approach first shows you understand the baseline, but implementing the prefix–suffix method shows strong algorithmic optimization skills.