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.lengthn == matrix[i].length2 <= m, n <= 50-1 <= matrix[i][j] <= 100The key idea in #3033 Modify the Matrix is to replace every -1 in the grid with the maximum value from its column. Since the replacement value depends only on the column, a useful strategy is to first determine the maximum element present in each column.
Traverse the matrix column by column (or compute while scanning rows) and store the maximum value for each column in a small auxiliary structure such as an array. Once these column maxima are known, iterate through the matrix again and update every cell containing -1 with the corresponding column’s maximum value.
This approach separates the problem into two simple passes: one to gather column statistics and another to perform replacements. The method is efficient because each cell is processed only a constant number of times. The overall time complexity is O(m × n), where m and n are the matrix dimensions, while the extra space required for storing column maxima is O(n).
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Precompute column maximums and replace -1 values | O(m × n) | O(n) |
Ashish Pratap Singh
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Problems involving matrix traversal and column or row preprocessing are common in coding interviews, including FAANG-style interviews. While this exact question may not always appear, the pattern of preprocessing matrix statistics is frequently tested.
An array (or vector) to store the maximum value of each column is sufficient. Since each column has a single maximum value needed for replacements, this structure allows quick lookups during the second pass through the matrix.
The optimal approach is to compute the maximum value for each column first and store it in an array. After that, scan the matrix again and replace every -1 with the maximum value of its column. This keeps the solution simple and efficient with linear time over all cells.
The time complexity is O(m × n) because every element in the matrix is visited at most twice—once to compute column maxima and once to replace -1 values. This makes the approach optimal for this problem.