Modify the Matrix

Easy

#2701Time: O(m^2 * n). The nested loops iterate through `m * n` cells. For each cell containing `-1`, we perform a column scan taking `O(m)` time. In the worst case, where a large fraction of cells are `-1`, the complexity is `O(m * n * m)`.Space: O(m * n). A new matrix `answer` of the same dimensions as the input is created, requiring space proportional to the number of elements.1 company

Data structures

Array Matrix

Companies

Fidelity

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly translates the problem statement into code. It involves creating a copy of the input matrix and then iterating through each cell of this new matrix. Whenever a cell with a value of -1 is found, a separate search is initiated within its corresponding column to find the maximum value. This maximum value then replaces the -1.

Algorithm

Get the dimensions of the matrix, m (rows) and n (columns).
Create a new m x n matrix, answer, as a deep copy of the input matrix.
Iterate through each cell (i, j) of the answer matrix.
If answer[i][j] is -1: a. Initialize a variable maxInCol to a very small number (e.g., -1, since all other numbers are non-negative). b. Initiate a new loop to scan the entire column j of the original matrix (from row k = 0 to m-1). c. In this inner loop, update maxInCol by comparing it with matrix[k][j]. d. After the column scan is complete, update the cell in the new matrix: answer[i][j] = maxInCol.
After iterating through all cells, return the answer matrix.

Walkthrough

The algorithm begins by creating an exact copy of the input matrix, let's call it answer. It then uses nested loops to traverse every element of answer. For each element, it checks if its value is -1. If it is, the algorithm performs another full scan of that element's column in the original matrix to find the maximum value. This maximum value is then used to replace the -1 in the answer matrix. This process is repeated for all elements. Using the original matrix for finding the maximum is crucial to avoid using a value that was just replaced in the same column's calculation.

1class Solution {2    public int[][] modifiedMatrix(int[][] matrix) {3        int m = matrix.length;4        int n = matrix[0].length;5        int[][] answer = new int[m][n];6 7        // Create a copy of the matrix8        for (int i = 0; i < m; i++) {9            for (int j = 0; j < n; j++) {10                answer[i][j] = matrix[i][j];11            }12        }13 14        // Iterate and replace -1s15        for (int i = 0; i < m; i++) {16            for (int j = 0; j < n; j++) {17                if (answer[i][j] == -1) {18                    int maxInCol = -1;19                    // Find the maximum in the current column from the original matrix20                    for (int k = 0; k < m; k++) {21                        maxInCol = Math.max(maxInCol, matrix[k][j]);22                    }23                    answer[i][j] = maxInCol;24                }25            }26        }27        return answer;28    }29}

Complexity

Time

O(m^2 * n). The nested loops iterate through `m * n` cells. For each cell containing `-1`, we perform a column scan taking `O(m)` time. In the worst case, where a large fraction of cells are `-1`, the complexity is `O(m * n * m)`.

Space

O(m * n). A new matrix `answer` of the same dimensions as the input is created, requiring space proportional to the number of elements.

Trade-offs

Pros

Simple to understand and implement as it directly follows the problem's logic.

Cons

Highly inefficient due to redundant computations. The maximum of a column is recalculated for every -1 found in that column, leading to a poor time complexity.

This is a more efficient approach that avoids the redundant calculations of the brute-force method. It works in two main phases. In the first pass, we iterate through the matrix once to determine the maximum value for each column and store these maximums in an auxiliary array. In the second pass, we build the result matrix, using the pre-computed maximums from the auxiliary array to replace any -1 values.

Algorithm

Get the matrix dimensions, m (rows) and n (columns).
Create a 1D auxiliary array, colMaxs, of size n.
First Pass: Iterate through each column j from 0 to n-1. a. For each column, find its maximum value by iterating through all its rows (i from 0 to m-1). b. Store the computed maximum in colMaxs[j].
Create the final answer matrix of size m x n.
Second Pass: Iterate through the original matrix from (0,0) to (m-1, n-1). a. For each cell (i, j), check if matrix[i][j] is -1. b. If it is, set answer[i][j] = colMaxs[j]. c. Otherwise, copy the value: answer[i][j] = matrix[i][j].
Return the answer matrix.

Walkthrough

The core idea is to pre-compute the maximum value for each column before attempting to modify the matrix. We start by creating an array, colMaxs, to hold these maximums. We then perform a full scan of the input matrix, column by column, to populate this colMaxs array. Once we have the maximum for every column, we create the new answer matrix. We then perform a second scan of the input matrix. During this scan, we populate the answer matrix: if an element in the input is -1, we fill the corresponding cell in answer with the pre-computed max from colMaxs; otherwise, we just copy the element's value. This eliminates the need to re-scan columns repeatedly.

1class Solution {2    public int[][] modifiedMatrix(int[][] matrix) {3        int m = matrix.length;4        int n = matrix[0].length;5 6        // Step 1: Find the maximum of each column7        int[] colMaxs = new int[n];8        for (int j = 0; j < n; j++) {9            int maxVal = -1;10            for (int i = 0; i < m; i++) {11                maxVal = Math.max(maxVal, matrix[i][j]);12            }13            colMaxs[j] = maxVal;14        }15 16        // Step 2: Create the answer matrix and fill it based on the pre-computed maxes17        int[][] answer = new int[m][n];18        for (int i = 0; i < m; i++) {19            for (int j = 0; j < n; j++) {20                if (matrix[i][j] == -1) {21                    answer[i][j] = colMaxs[j];22                } else {23                    answer[i][j] = matrix[i][j];24                }25            }26        }27 28        return answer;29    }30}

Complexity

Time

O(m * n). The first pass to find all column maximums takes `O(m * n)`. The second pass to construct the `answer` matrix also takes `O(m * n)`. The total time complexity is `O(m * n) + O(m * n)`, which simplifies to `O(m * n)`.

Space

O(m * n). We use `O(n)` extra space for the `colMaxs` array and `O(m * n)` space for the `answer` matrix. The space for the `answer` matrix is the dominant factor.

Trade-offs

Pros

Significantly more efficient than the brute-force approach, with a linear time complexity relative to the matrix size.
Avoids redundant work by pre-calculating column maximums.

Cons

Requires a small amount of extra space (O(n)) for the auxiliary array to store column maximums.
Requires two separate passes over the matrix data.

Solutions

Solution

1public class Solution {2    public int[][] ModifiedMatrix(int[][] matrix) {3        int m = matrix.Length, n = matrix[0].Length;4        for (int j = 0; j < n; ++j) {5            int mx = -1;6            for (int i = 0; i < m; ++i) {7                mx = Math.Max(mx, matrix[i][j]);8            }9            for (int i = 0; i < m; ++i) {10                if (matrix[i][j] == -1) {11                    matrix[i][j] = mx;12                }13            }14        }15        return matrix;16    }17}

1class Solution {2public3  int[][] modifiedMatrix(int[][] matrix) {4    int m = matrix.length, n = matrix[0].length;5    for (int j = 0; j < n; ++j) {6      int mx = -1;7      for (int i = 0; i < m; ++i) {8        mx = Math.max(mx, matrix[i][j]);9      }10      for (int i = 0; i < m; ++i) {11        if (matrix[i][j] == -1) {12          matrix[i][j] = mx;13        }14      }15    }16    return matrix;17  }18}

1class Solution {2public:3  vector<vector<int>> modifiedMatrix(vector<vector<int>> &matrix) {4    int m = matrix.size(), n = matrix[0].size();5    for (int j = 0; j < n; ++j) {6      int mx = -1;7      for (int i = 0; i < m; ++i) {8        mx = max(mx, matrix[i][j]);9      }10      for (int i = 0; i < m; ++i) {11        if (matrix[i][j] == -1) {12          matrix[i][j] = mx;13        }14      }15    }16    return matrix;17  }18};

1class Solution:2    def modifiedMatrix(self, matrix: List[List[int]]) -> List[List[int]]: m, n = len(matrix), len(matrix[0]) for j in range(n): mx = max(matrix[i][j] for i in range(m)) for i in range(m): if matrix[i][j] == - 1: matrix[i][j] = mx return matrix

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem