Watch 10 video solutions for Modify the Matrix, a easy level problem involving Array, Matrix. This walkthrough by CodingNinja has 579 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |