LeetCode Solutions Blog

Construct Product Matrix

Number: 3031

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given a 2D matrix grid of size n x m, construct a new matrix p such that each element p[i][j] is the product (modulo 12345) of all elements in grid except grid[i][j].

Key Insights

The total number of elements is nm (with nm <= 10^5), so it is efficient to flatten the grid into a one-dimensional array.
Instead of dividing the global product by a specific element (which is problematic modulo a composite number), compute prefix and suffix products.
The product excluding an element at index i can be obtained by multiplying the product of all elements before i and all elements after i.
Use modular arithmetic at each multiplication step to keep numbers within bounds.

Space and Time Complexity

Time Complexity: O(nm)
Space Complexity: O(nm)

Solution

The solution involves first flattening the 2D matrix into a 1D array. Then, two auxiliary arrays (prefix and suffix) are used.

The prefix array holds the product of all elements from the start up to the current index (modulo 12345).
The suffix array holds the product of all elements from the end down to the current index (modulo 12345).
For each index i, the answer is (prefix[i-1] * suffix[i+1]) modulo 12345, where boundary conditions are handled appropriately. Finally, the 1D solution is mapped back to a 2D matrix.

Code Solutions

# Python Code Solution

def constructProductMatrix(grid):
    mod = 12345
    # Flatten grid into a 1D list
    flat_list = [num for row in grid for num in row]
    n = len(flat_list)
    
    # Initialize prefix and suffix product arrays
    prefix = [1] * n
    suffix = [1] * n
    
    # Compute prefix products: prefix[i] = product of flat_list[0 .. i] mod mod
    prefix[0] = flat_list[0] % mod
    for i in range(1, n):
        prefix[i] = (prefix[i-1] * flat_list[i]) % mod
    
    # Compute suffix products: suffix[i] = product of flat_list[i .. n-1] mod mod
    suffix[n-1] = flat_list[n-1] % mod
    for i in range(n-2, -1, -1):
        suffix[i] = (suffix[i+1] * flat_list[i]) % mod
    
    # Initialize result array same size as grid
    result = []
    rows = len(grid)
    cols = len(grid[0])
    index = 0
    for i in range(rows):
        row_result = []
        for j in range(cols):
            # For each element, product of all except current = prefix[i-1] * suffix[i+1]
            left_product = prefix[index-1] if index > 0 else 1
            right_product = suffix[index+1] if index < n-1 else 1
            row_result.append((left_product * right_product) % mod)
            index += 1
        result.append(row_result)
    
    return result

# Example usage:
# grid = [[1,2],[3,4]]
# print(constructProductMatrix(grid))  # Output: [[24,12],[8,6]]