Jobs

Interviews

Discussions

Construct Product Matrix

Medium

Asked by:

4 views

Topics:

Arrays

Given a 0-indexed 2D integer matrix grid of size n * m, we define a 0-indexed 2D matrix p of size n * m as the product matrix of grid if the following condition is met:

Each element p[i][j] is calculated as the product of all elements in grid except for the element grid[i][j]. This product is then taken modulo 12345.

Return the product matrix of grid.

Example 1:

Input: grid = [[1,2],[3,4]]
Output: [[24,12],[8,6]]
Explanation: p[0][0] = grid[0][1] * grid[1][0] * grid[1][1] = 2 * 3 * 4 = 24
p[0][1] = grid[0][0] * grid[1][0] * grid[1][1] = 1 * 3 * 4 = 12
p[1][0] = grid[0][0] * grid[0][1] * grid[1][1] = 1 * 2 * 4 = 8
p[1][1] = grid[0][0] * grid[0][1] * grid[1][0] = 1 * 2 * 3 = 6
So the answer is [[24,12],[8,6]].

Example 2:

Input: grid = [[12345],[2],[1]]
Output: [[2],[0],[0]]
Explanation: p[0][0] = grid[0][1] * grid[0][2] = 2 * 1 = 2.
p[0][1] = grid[0][0] * grid[0][2] = 12345 * 1 = 12345. 12345 % 12345 = 0. So p[0][1] = 0.
p[0][2] = grid[0][0] * grid[0][1] = 12345 * 2 = 24690. 24690 % 12345 = 0. So p[0][2] = 0.
So the answer is [[2],[0],[0]].

Constraints:

1 <= n == grid.length <= 10⁵
1 <= m == grid[i].length <= 10⁵
2 <= n * m <= 10⁵
1 <= grid[i][j] <= 10⁹

Try coding it in LeetCode

Construct Product Matrix

Medium

Asked by:

4 views

Topics:

Arrays

Given a 0-indexed 2D integer matrix grid of size n * m, we define a 0-indexed 2D matrix p of size n * m as the product matrix of grid if the following condition is met:

Each element p[i][j] is calculated as the product of all elements in grid except for the element grid[i][j]. This product is then taken modulo 12345.

Return the product matrix of grid.

Example 1:

Input: grid = [[1,2],[3,4]]
Output: [[24,12],[8,6]]
Explanation: p[0][0] = grid[0][1] * grid[1][0] * grid[1][1] = 2 * 3 * 4 = 24
p[0][1] = grid[0][0] * grid[1][0] * grid[1][1] = 1 * 3 * 4 = 12
p[1][0] = grid[0][0] * grid[0][1] * grid[1][1] = 1 * 2 * 4 = 8
p[1][1] = grid[0][0] * grid[0][1] * grid[1][0] = 1 * 2 * 3 = 6
So the answer is [[24,12],[8,6]].

Example 2:

Input: grid = [[12345],[2],[1]]
Output: [[2],[0],[0]]
Explanation: p[0][0] = grid[0][1] * grid[0][2] = 2 * 1 = 2.
p[0][1] = grid[0][0] * grid[0][2] = 12345 * 1 = 12345. 12345 % 12345 = 0. So p[0][1] = 0.
p[0][2] = grid[0][0] * grid[0][1] = 12345 * 2 = 24690. 24690 % 12345 = 0. So p[0][2] = 0.
So the answer is [[2],[0],[0]].

Constraints:

1 <= n == grid.length <= 10⁵
1 <= m == grid[i].length <= 10⁵
2 <= n * m <= 10⁵
1 <= grid[i][j] <= 10⁹

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

The calculation for `p[i][j]` involves a division-like operation under a composite modulo, `12345`. Since a modular inverse might not exist for some grid values, how should I handle such cases?
The second example includes `12345`, the modulus value, itself as an input. Could you clarify the expected behavior if the input grid contains two or more numbers that are multiples of `12345`?
The values in the grid can be up to 10^9. When calculating the running product, an intermediate multiplication could overflow a standard 32-bit integer. Should I plan on using a 64-bit integer type to prevent this?
The problem describes the input as an `n * m` grid. Can I assume the grid is always rectangular, meaning all rows will have the same length `m`?
Regarding the output format, does the function need to return a newly allocated matrix, or is it acceptable to modify the input `grid` in-place?

Brute Force Solution

Approach

To build the new grid of numbers, we calculate the value for each spot individually. For any given spot, the most direct method is to look at the original grid and multiply all of its numbers together, but deliberately skipping the number that was in the same spot we are currently trying to calculate.

Here's how the algorithm would work step-by-step:

Let's focus on filling in just one single spot in our new grid.
To find its value, we'll start a running product, beginning with the number one.
Now, we'll go through every single number in the original grid, from the first row to the last.
For each number we see, we'll multiply it into our running product.
There's one exception: if the number we're looking at in the original grid is in the exact same position as the spot we're currently trying to fill, we just ignore it and move on.
After we've gone through the entire original grid this way, the final running product is the value for that one spot in our new grid.
We then repeat this entire process for every single spot in the new grid until it's completely filled.
We also apply a special math rule after each multiplication to ensure our running product doesn't become excessively large.

Code Implementation

def construct_product_matrix(grid):
    number_of_rows = len(grid)
    number_of_columns = len(grid[0])
    modulus = 12345

    # Create a new grid of the same size, initialized to zero, to store the results.

    result_matrix = [[0] * number_of_columns for _ in range(number_of_rows)]

    # We must iterate through each cell of the matrix we are trying to construct.

    for target_row in range(number_of_rows):
        for target_column in range(number_of_columns):

            # Reset the product to 1 for each new cell because it is the multiplicative identity.

            product_for_target_cell = 1

            # For each target cell, scan the entire original grid to calculate the product of other elements.

            for source_row in range(number_of_rows):
                for source_column in range(number_of_columns):
                    if source_row == target_row and source_column == target_column:
                        continue

                    product_for_target_cell *= grid[source_row][source_column]
                    product_for_target_cell %= modulus

            result_matrix[target_row][target_column] = product_for_target_cell

    return result_matrix

Big(O) Analysis

Time Complexity

O(N^2) – The time complexity is driven by a nested iteration over the grid's elements. For each cell in the n x m output grid, the algorithm iterates through every cell of the n x m input grid to calculate the required product. If we let N be the total number of elements in the grid (N = n * m), this means for each of the N output cells, we perform approximately N multiplications. This results in a total operation count proportional to N * N, which simplifies to O(N^2).

Space Complexity

O(N) – The primary use of auxiliary space comes from constructing the 'new grid' to store the results, as described in the first step. Let N be the total number of elements in the input grid (rows * columns); this new grid requires space for N elements. While the calculation for each spot uses a temporary variable for the 'running product', this is a constant amount of space. Thus, the dominant factor is the result grid, leading to space usage proportional to the input size N.

Optimal Solution

Approach

To find the product of all numbers except one for each spot in a grid, we avoid repetitive work. The key is to make two sweeps across the grid: one from the beginning to end, calculating the product of numbers 'before' each spot, and another from end to beginning for numbers 'after' each spot. Combining these two results gives us the answer for each spot efficiently.

Here's how the algorithm would work step-by-step:

First, imagine all the numbers in the grid as if they were in one long line, read from left-to-right and top-to-bottom.
We will build our final answer grid in two main stages. For the first stage, we'll calculate the product of all numbers that come *before* any given spot in that long line.
We do this by moving from the start to the end of the line. We keep a running total of the product of numbers seen so far. For each spot, we record this running product in our new grid, then update the running product by multiplying in the number from the spot we just visited.
After this first sweep, every position in our new grid contains the product of all the numbers that came before it.
Next, we'll do a second sweep, this time from the end of the line back to the start. We'll use another running product for this direction.
On this backward journey, for each spot, we multiply the number already in our new grid by our backward-running product. This combines the 'product of everything before' with the 'product of everything after'.
After this second sweep, our new grid is complete. Each spot now correctly holds the product of every number except for the one originally at that spot. All calculations are done using special modulo math to keep the numbers manageable.

Code Implementation

def construct_product_matrix(grid: list[list[int]]) -> list[list[int]]:
    number_of_rows = len(grid)
    number_of_columns = len(grid[0])
    MODULO = 12345

    product_matrix = [[1] * number_of_columns for _ in range(number_of_rows)]

    # The first pass computes prefix products, storing the product of all elements before each cell.
    prefix_product = 1
    for row_index in range(number_of_rows):
        for column_index in range(number_of_columns):
            product_matrix[row_index][column_index] = prefix_product
            prefix_product = (prefix_product * grid[row_index][column_index]) % MODULO

    # The second pass computes suffix products and combines them with the stored prefix products.
    suffix_product = 1
    for row_index in range(number_of_rows - 1, -1, -1):
        for column_index in range(number_of_columns - 1, -1, -1):
            # The final value is the stored prefix product multiplied by the current suffix product.
            product_matrix[row_index][column_index] = (product_matrix[row_index][column_index] * suffix_product) % MODULO
            suffix_product = (suffix_product * grid[row_index][column_index]) % MODULO

    return product_matrix

Big(O) Analysis

Time Complexity

O(m * n) – The time complexity is determined by two full traversals of the input grid. Let's say the grid has m rows and n columns, for a total of m * n elements. The first pass iterates through all m * n elements from start to finish to calculate the prefix products for each position. The second pass then iterates through the same m * n elements again, but from finish to start, to incorporate the suffix products. The total number of operations is directly proportional to (m * n) + (m * n), which simplifies to O(m * n).

Space Complexity

O(1) – The space complexity is determined by the extra memory used besides the output matrix. The plain English explanation describes using a 'running total of the product' for the forward pass and another 'running product' for the backward pass. These are implemented as a few variables whose memory usage does not scale with the total number of elements, N, in the grid. Since this extra memory is constant, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Cumulative product overflow	Apply the modulo operation after each multiplication step to ensure the running product remains within a manageable range.
Overflow within a single multiplication step	Use a 64-bit integer type for calculations like (a * b) % m to prevent intermediate values from overflowing a 32-bit integer.
Grid elements being multiples of the modulus	These elements are correctly treated as 0 modulo 12345, causing any product that includes them to also become 0.
Grid elements sharing prime factors with the modulus	A prefix-suffix product approach avoids division, bypassing issues with non-existent modular multiplicative inverses for certain numbers.
Maximum grid size leading to Time Limit Exceeded	The solution must have a linear time complexity, O(n*m), to process up to 10^5 elements efficiently.
Minimum grid size (two elements)	The prefix-suffix logic must correctly handle the boundaries for the first and last elements, which have no preceding or succeeding elements respectively.
Highly skewed grid dimensions	Flattening the grid into a 1D array makes the algorithm robust and independent of the specific n and m values.
Inputs violating stated constraints	A production-ready solution should clarify how to handle invalid inputs like null or improperly sized grids, possibly by throwing an error.

Cumulative product overflow

How to Handle:

Apply the modulo operation after each multiplication step to ensure the running product remains within a manageable range.

Overflow within a single multiplication step

How to Handle:

Use a 64-bit integer type for calculations like (a * b) % m to prevent intermediate values from overflowing a 32-bit integer.

Grid elements being multiples of the modulus

How to Handle:

These elements are correctly treated as 0 modulo 12345, causing any product that includes them to also become 0.

Grid elements sharing prime factors with the modulus

How to Handle:

A prefix-suffix product approach avoids division, bypassing issues with non-existent modular multiplicative inverses for certain numbers.

Maximum grid size leading to Time Limit Exceeded

How to Handle:

The solution must have a linear time complexity, O(n*m), to process up to 10^5 elements efficiently.

Minimum grid size (two elements)

How to Handle:

The prefix-suffix logic must correctly handle the boundaries for the first and last elements, which have no preceding or succeeding elements respectively.

Highly skewed grid dimensions

How to Handle:

Flattening the grid into a 1D array makes the algorithm robust and independent of the specific n and m values.

Inputs violating stated constraints

How to Handle:

A production-ready solution should clarify how to handle invalid inputs like null or improperly sized grids, possibly by throwing an error.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

The calculation for `p[i][j]` involves a division-like operation under a composite modulo, `12345`. Since a modular inverse might not exist for some grid values, how should I handle such cases?
The second example includes `12345`, the modulus value, itself as an input. Could you clarify the expected behavior if the input grid contains two or more numbers that are multiples of `12345`?
The values in the grid can be up to 10^9. When calculating the running product, an intermediate multiplication could overflow a standard 32-bit integer. Should I plan on using a 64-bit integer type to prevent this?
The problem describes the input as an `n * m` grid. Can I assume the grid is always rectangular, meaning all rows will have the same length `m`?
Regarding the output format, does the function need to return a newly allocated matrix, or is it acceptable to modify the input `grid` in-place?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Let's focus on filling in just one single spot in our new grid.
To find its value, we'll start a running product, beginning with the number one.
Now, we'll go through every single number in the original grid, from the first row to the last.
For each number we see, we'll multiply it into our running product.
There's one exception: if the number we're looking at in the original grid is in the exact same position as the spot we're currently trying to fill, we just ignore it and move on.
After we've gone through the entire original grid this way, the final running product is the value for that one spot in our new grid.
We then repeat this entire process for every single spot in the new grid until it's completely filled.
We also apply a special math rule after each multiplication to ensure our running product doesn't become excessively large.

Code Implementation

def construct_product_matrix(grid):
    number_of_rows = len(grid)
    number_of_columns = len(grid[0])
    modulus = 12345

    # Create a new grid of the same size, initialized to zero, to store the results.

    result_matrix = [[0] * number_of_columns for _ in range(number_of_rows)]

    # We must iterate through each cell of the matrix we are trying to construct.

    for target_row in range(number_of_rows):
        for target_column in range(number_of_columns):

            # Reset the product to 1 for each new cell because it is the multiplicative identity.

            product_for_target_cell = 1

            # For each target cell, scan the entire original grid to calculate the product of other elements.

            for source_row in range(number_of_rows):
                for source_column in range(number_of_columns):
                    if source_row == target_row and source_column == target_column:
                        continue

                    product_for_target_cell *= grid[source_row][source_column]
                    product_for_target_cell %= modulus

            result_matrix[target_row][target_column] = product_for_target_cell

    return result_matrix

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, imagine all the numbers in the grid as if they were in one long line, read from left-to-right and top-to-bottom.
We will build our final answer grid in two main stages. For the first stage, we'll calculate the product of all numbers that come *before* any given spot in that long line.
We do this by moving from the start to the end of the line. We keep a running total of the product of numbers seen so far. For each spot, we record this running product in our new grid, then update the running product by multiplying in the number from the spot we just visited.
After this first sweep, every position in our new grid contains the product of all the numbers that came before it.
Next, we'll do a second sweep, this time from the end of the line back to the start. We'll use another running product for this direction.
On this backward journey, for each spot, we multiply the number already in our new grid by our backward-running product. This combines the 'product of everything before' with the 'product of everything after'.
After this second sweep, our new grid is complete. Each spot now correctly holds the product of every number except for the one originally at that spot. All calculations are done using special modulo math to keep the numbers manageable.

Code Implementation

def construct_product_matrix(grid: list[list[int]]) -> list[list[int]]:
    number_of_rows = len(grid)
    number_of_columns = len(grid[0])
    MODULO = 12345

    product_matrix = [[1] * number_of_columns for _ in range(number_of_rows)]

    # The first pass computes prefix products, storing the product of all elements before each cell.
    prefix_product = 1
    for row_index in range(number_of_rows):
        for column_index in range(number_of_columns):
            product_matrix[row_index][column_index] = prefix_product
            prefix_product = (prefix_product * grid[row_index][column_index]) % MODULO

    # The second pass computes suffix products and combines them with the stored prefix products.
    suffix_product = 1
    for row_index in range(number_of_rows - 1, -1, -1):
        for column_index in range(number_of_columns - 1, -1, -1):
            # The final value is the stored prefix product multiplied by the current suffix product.
            product_matrix[row_index][column_index] = (product_matrix[row_index][column_index] * suffix_product) % MODULO
            suffix_product = (suffix_product * grid[row_index][column_index]) % MODULO

    return product_matrix

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Cumulative product overflow	Apply the modulo operation after each multiplication step to ensure the running product remains within a manageable range.
Overflow within a single multiplication step	Use a 64-bit integer type for calculations like (a * b) % m to prevent intermediate values from overflowing a 32-bit integer.
Grid elements being multiples of the modulus	These elements are correctly treated as 0 modulo 12345, causing any product that includes them to also become 0.
Grid elements sharing prime factors with the modulus	A prefix-suffix product approach avoids division, bypassing issues with non-existent modular multiplicative inverses for certain numbers.
Maximum grid size leading to Time Limit Exceeded	The solution must have a linear time complexity, O(n*m), to process up to 10^5 elements efficiently.
Minimum grid size (two elements)	The prefix-suffix logic must correctly handle the boundaries for the first and last elements, which have no preceding or succeeding elements respectively.
Highly skewed grid dimensions	Flattening the grid into a 1D array makes the algorithm robust and independent of the specific n and m values.
Inputs violating stated constraints	A production-ready solution should clarify how to handle invalid inputs like null or improperly sized grids, possibly by throwing an error.

Cumulative product overflow

How to Handle:

Apply the modulo operation after each multiplication step to ensure the running product remains within a manageable range.

Overflow within a single multiplication step

How to Handle:

Use a 64-bit integer type for calculations like (a * b) % m to prevent intermediate values from overflowing a 32-bit integer.

Grid elements being multiples of the modulus

How to Handle:

These elements are correctly treated as 0 modulo 12345, causing any product that includes them to also become 0.

Grid elements sharing prime factors with the modulus

How to Handle:

A prefix-suffix product approach avoids division, bypassing issues with non-existent modular multiplicative inverses for certain numbers.

Maximum grid size leading to Time Limit Exceeded

How to Handle:

The solution must have a linear time complexity, O(n*m), to process up to 10^5 elements efficiently.

Minimum grid size (two elements)

How to Handle:

The prefix-suffix logic must correctly handle the boundaries for the first and last elements, which have no preceding or succeeding elements respectively.

Highly skewed grid dimensions

How to Handle:

Flattening the grid into a 1D array makes the algorithm robust and independent of the specific n and m values.

Inputs violating stated constraints

How to Handle:

A production-ready solution should clarify how to handle invalid inputs like null or improperly sized grids, possibly by throwing an error.