Jobs

Interviews

Discussions

Modify the Matrix

#1 Most AskedEasy

Modify the Matrix #1 Most Asked

Easy

Fidelity Investments

26 views

Topics:

Arrays

Given a 0-indexed m x n integer matrix matrix, create a new 0-indexed matrix called answer. Make answer equal to matrix, then replace each element with the value -1 with the maximum element in its respective column.

Return the matrix answer.

Example 1:

Input: matrix = [[1,2,-1],[4,-1,6],[7,8,9]]
Output: [[1,2,9],[4,8,6],[7,8,9]]
Explanation: The diagram above shows the elements that are changed (in blue).
- We replace the value in the cell [1][1] with the maximum value in the column 1, that is 8.
- We replace the value in the cell [0][2] with the maximum value in the column 2, that is 9.

Example 2:

Input: matrix = [[3,-1],[5,2]]
Output: [[3,2],[5,2]]
Explanation: The diagram above shows the elements that are changed (in blue).

Constraints:

m == matrix.length
n == matrix[i].length
2 <= m, n <= 50
-1 <= matrix[i][j] <= 100
The input is generated such that each column contains at least one non-negative integer.

Try coding it in LeetCode

Modify the Matrix

#1 Most AskedEasy

Modify the Matrix #1 Most Asked

Easy

Fidelity Investments

26 views

Topics:

Arrays

Return the matrix answer.

Example 1:

Input: matrix = [[1,2,-1],[4,-1,6],[7,8,9]]
Output: [[1,2,9],[4,8,6],[7,8,9]]
Explanation: The diagram above shows the elements that are changed (in blue).
- We replace the value in the cell [1][1] with the maximum value in the column 1, that is 8.
- We replace the value in the cell [0][2] with the maximum value in the column 2, that is 9.

Example 2:

Input: matrix = [[3,-1],[5,2]]
Output: [[3,2],[5,2]]
Explanation: The diagram above shows the elements that are changed (in blue).

Constraints:

m == matrix.length
n == matrix[i].length
2 <= m, n <= 50
-1 <= matrix[i][j] <= 100
The input is generated such that each column contains at least one non-negative integer.

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:

Is -1 the only placeholder, and are the other values guaranteed to be greater than -1?
Is every column guaranteed to contain at least one real value, so a column maximum always exists?
Should the original grid be changed, or should a separate grid be returned?
Can the grid have a single row or a single cell?
If several cells in a column are placeholders, should they all receive that same column maximum?

Brute Force Solution

Approach

Build a fresh copy of the grid so the original values stay available while the answer is filled in. For each column, find the largest real value, then write that value into every placeholder in the copy of that column.

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

Make a copy of the grid so replacements do not hide the original numbers.
Look at one column at a time.
Scan that column and remember the largest value in it.
Scan the column again and, wherever the original cell is a placeholder, write the remembered maximum into the copy.
Move to the next column and repeat.
Return the copy once every column has been filled.

Code Implementation

class Solution:
    def modifiedMatrix(self, matrix):
        num_rows = len(matrix)
        num_cols = len(matrix[0])

        # A new grid is needed to store the results without altering the original during calculation.
        answer_matrix = [[0] * num_cols for _ in range(num_rows)]
        for row_index in range(num_rows):
            for col_index in range(num_cols):
                answer_matrix[row_index][col_index] = matrix[row_index][col_index]

        # We must iterate column by column to find each column's maximum value independently.
        for col_index in range(num_cols):
            max_value_in_column = -1
            for row_index in range(num_rows):
                if matrix[row_index][col_index] > max_value_in_column:
                    max_value_in_column = matrix[row_index][col_index]

            # After finding the max, this second pass through the column updates only the placeholders.
            for row_index in range(num_rows):
                if matrix[row_index][col_index] == -1:
                    answer_matrix[row_index][col_index] = max_value_in_column

        return answer_matrix

Big(O) Analysis

Time Complexity

O(m * n) – Copying the grid visits every cell once. Each column is then scanned twice, once to find its largest value and once to fill placeholders, and together those scans also visit every cell a constant number of times. If the grid has m rows and n columns, the work is proportional to m * n, which is O(m * n).

Space Complexity

O(m * n) – A full second grid is allocated so the original values remain available while the answer is written. That copy contains one cell for every cell of the input, so its size grows with both dimensions. The auxiliary space is therefore O(m * n), where m is the number of rows and n is the number of columns.

Optimal Solution

Approach

The column maximums can be collected in one pass and stored in a short list, one maximum per column. A second pass then writes each maximum into the placeholder cells of that column, updating the grid in place.

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

If the grid is empty, return it unchanged.
For each column, scan every row and remember the largest value.
Store that maximum in a list, in column order.
Walk the grid again, and wherever a cell is a placeholder, replace it with the stored maximum for its column.
Leave real values untouched.
Return the same grid after the placeholders have been filled.

Code Implementation

def modified_matrix(matrix):
    if not matrix or not matrix[0]:
        return matrix

    number_of_rows = len(matrix)
    number_of_columns = len(matrix[0])
    
    # This array will store the maximum value found in each column to use for replacements later.
    column_maximums = [0] * number_of_columns

    # The first pass identifies the maximum value in each column.
    for column_index in range(number_of_columns):
        current_column_max = -1
        for row_index in range(number_of_rows):
            current_column_max = max(current_column_max, matrix[row_index][column_index])
        column_maximums[column_index] = current_column_max

    # The second pass modifies the matrix, filling in -1 placeholders with their column's max.
    for row_index in range(number_of_rows):
        for column_index in range(number_of_columns):
            if matrix[row_index][column_index] == -1:
                matrix[row_index][column_index] = column_maximums[column_index]
    
    return matrix

Big(O) Analysis

Time Complexity

O(m * n) – The first pass finds a maximum for every column by reading every cell. The second pass writes placeholders by reading every cell again. Both passes are proportional to the number of cells. With m rows and n columns, that is O(m * n).

Space Complexity

O(n) – Besides the grid itself, the algorithm stores one maximum for each column. That list grows with the number of columns, n, and does not grow with the number of rows. The grid is updated in place, so the auxiliary space is O(n).

Edge Cases

Case	How to Handle
The grid is a single cell that is already a real value	Leave the cell unchanged, because there is no placeholder to replace.
A column contains several placeholders	Every placeholder in that column is replaced with the same column maximum.
The maximum is the only non-placeholder in the column	The placeholders still receive that value, since one real value is enough to define the maximum.
The grid has a single row	Each placeholder is replaced by the only real value in its column, which is the column maximum.
A cell is already equal to the column maximum	It stays as it is, because only placeholder cells are rewritten.

The grid is a single cell that is already a real value

How to Handle:

Leave the cell unchanged, because there is no placeholder to replace.

A column contains several placeholders

How to Handle:

Every placeholder in that column is replaced with the same column maximum.

The maximum is the only non-placeholder in the column

How to Handle:

The placeholders still receive that value, since one real value is enough to define the maximum.

The grid has a single row

How to Handle:

Each placeholder is replaced by the only real value in its column, which is the column maximum.

A cell is already equal to the column maximum

How to Handle:

It stays as it is, because only placeholder cells are rewritten.

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:

Is -1 the only placeholder, and are the other values guaranteed to be greater than -1?
Is every column guaranteed to contain at least one real value, so a column maximum always exists?
Should the original grid be changed, or should a separate grid be returned?
Can the grid have a single row or a single cell?
If several cells in a column are placeholders, should they all receive that same column maximum?

Brute Force Solution

Approach

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

Make a copy of the grid so replacements do not hide the original numbers.
Look at one column at a time.
Scan that column and remember the largest value in it.
Scan the column again and, wherever the original cell is a placeholder, write the remembered maximum into the copy.
Move to the next column and repeat.
Return the copy once every column has been filled.

Code Implementation

class Solution:
    def modifiedMatrix(self, matrix):
        num_rows = len(matrix)
        num_cols = len(matrix[0])

        # A new grid is needed to store the results without altering the original during calculation.
        answer_matrix = [[0] * num_cols for _ in range(num_rows)]
        for row_index in range(num_rows):
            for col_index in range(num_cols):
                answer_matrix[row_index][col_index] = matrix[row_index][col_index]

        # We must iterate column by column to find each column's maximum value independently.
        for col_index in range(num_cols):
            max_value_in_column = -1
            for row_index in range(num_rows):
                if matrix[row_index][col_index] > max_value_in_column:
                    max_value_in_column = matrix[row_index][col_index]

            # After finding the max, this second pass through the column updates only the placeholders.
            for row_index in range(num_rows):
                if matrix[row_index][col_index] == -1:
                    answer_matrix[row_index][col_index] = max_value_in_column

        return answer_matrix

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

If the grid is empty, return it unchanged.
For each column, scan every row and remember the largest value.
Store that maximum in a list, in column order.
Walk the grid again, and wherever a cell is a placeholder, replace it with the stored maximum for its column.
Leave real values untouched.
Return the same grid after the placeholders have been filled.

Code Implementation

def modified_matrix(matrix):
    if not matrix or not matrix[0]:
        return matrix

    number_of_rows = len(matrix)
    number_of_columns = len(matrix[0])
    
    # This array will store the maximum value found in each column to use for replacements later.
    column_maximums = [0] * number_of_columns

    # The first pass identifies the maximum value in each column.
    for column_index in range(number_of_columns):
        current_column_max = -1
        for row_index in range(number_of_rows):
            current_column_max = max(current_column_max, matrix[row_index][column_index])
        column_maximums[column_index] = current_column_max

    # The second pass modifies the matrix, filling in -1 placeholders with their column's max.
    for row_index in range(number_of_rows):
        for column_index in range(number_of_columns):
            if matrix[row_index][column_index] == -1:
                matrix[row_index][column_index] = column_maximums[column_index]
    
    return matrix

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
The grid is a single cell that is already a real value	Leave the cell unchanged, because there is no placeholder to replace.
A column contains several placeholders	Every placeholder in that column is replaced with the same column maximum.
The maximum is the only non-placeholder in the column	The placeholders still receive that value, since one real value is enough to define the maximum.
The grid has a single row	Each placeholder is replaced by the only real value in its column, which is the column maximum.
A cell is already equal to the column maximum	It stays as it is, because only placeholder cells are rewritten.

The grid is a single cell that is already a real value

How to Handle:

Leave the cell unchanged, because there is no placeholder to replace.

A column contains several placeholders

How to Handle:

Every placeholder in that column is replaced with the same column maximum.

The maximum is the only non-placeholder in the column

How to Handle:

The placeholders still receive that value, since one real value is enough to define the maximum.

The grid has a single row

How to Handle:

Each placeholder is replaced by the only real value in its column, which is the column maximum.

A cell is already equal to the column maximum

How to Handle:

It stays as it is, because only placeholder cells are rewritten.

0/2 Fidelity Investments questions completed

0/2 completed