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] <= 100Problem Overview: You are given an m x n matrix where some cells contain -1. Each -1 must be replaced with the maximum value present in its column. All other values remain unchanged. The task is simply transforming the matrix using column information.
Approach 1: Direct Replacement with Dynamic Maximum Finding (O(m^2 * n) time, O(1) space)
The straightforward method scans the column every time you encounter a -1. Iterate through the matrix row by row. When a cell equals -1, iterate through the same column to compute the maximum value, then replace the cell with that value. This avoids extra memory but repeats the same column scans many times. In the worst case, every cell is -1, causing a full column scan for each position. The result is roughly O(m^2 * n) time complexity with constant auxiliary space.
This approach works for small matrices and is useful for demonstrating the basic logic of the problem. However, it becomes inefficient when many replacements are required because the same column maximum is recomputed repeatedly.
Approach 2: Single Pass with Precomputed Column Maximums (O(m * n) time, O(n) space)
A more efficient approach precomputes the maximum value of every column before performing replacements. First, iterate through the matrix once and store the maximum value for each column in an array of size n. This step takes O(m * n) time. Next, perform a second pass over the matrix and replace every -1 with the corresponding column maximum stored in the array.
This removes redundant work because each column maximum is calculated only once. The algorithm processes each cell a constant number of times, resulting in O(m * n) time complexity and O(n) extra space for the column maximum array.
The solution relies purely on sequential traversal of a array-based grid structure and column-wise aggregation typical in matrix problems. The key insight is recognizing that column maximum values are independent of row order, so they can be computed once and reused.
Recommended for interviews: The precomputed column maximum approach is what interviewers expect. It shows that you recognize repeated work and optimize it with a simple preprocessing step. Mentioning the dynamic scan approach first demonstrates baseline reasoning, but implementing the O(m * n) solution shows strong problem‑solving instincts.
This approach involves first calculating the maximum value for each column and storing it, then iterating through the matrix a second time to replace each -1 with the column maximum.
The function modifyMatrix first calculates the maximums of each column and stores them in an array col_max. It then iterates over the matrix again to replace any occurrences of -1 with the corresponding column maximum value.
Time Complexity: O(m * n), where m and n are the matrix dimensions. The matrix is traversed twice.
Space Complexity: O(n), where n is the number of columns, due to the extra space for storing column maximums.
This approach repeatedly replaces -1 elements with the maximum found in their column on-the-fly during traversal. This minimizes space usage by not requiring additional storage for column maximums before replacements but is less efficient in the time domain.
The on-the-fly approach calculates the column maximum in each column every time it encounters a -1. This avoids an initial pass to compute all column maximums but comes at the cost of recomputation.
Python
Java
JavaScript
Time Complexity: O(m2 * n), due to recalculating column maxima during each replacement.
Space Complexity: O(1), no additional space used beyond input matrix.
We can follow the problem description, traverse each column, find the maximum value of each column, and then traverse each column again, replacing the elements with a value of -1 with the maximum value of that column.
The time complexity is O(m times n), where m and n are the number of rows and columns of the matrix, respectively. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Single Pass Approach with Precomputed Column Maximums | Time Complexity: O(m * n), where m and n are the matrix dimensions. The matrix is traversed twice. |
| Direct Replacement with Dynamic Maximum Finding | Time Complexity: O(m2 * n), due to recalculating column maxima during each replacement. |
| Simulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Replacement with Dynamic Maximum Finding | O(m^2 * n) | O(1) | Useful for understanding the problem or when avoiding extra memory is required |
| Single Pass with Precomputed Column Maximums | O(m * n) | O(n) | Best general solution; avoids repeated column scans and is optimal for interviews |
3033. Modify the Matrix - LeetCode Weekly Contest 384 | Python, JavaScript, Java, C++ • CodingNinja • 579 views views
Watch 9 more video solutions →Practice Modify the Matrix with our built-in code editor and test cases.
Practice on FleetCode