Modify the Matrix solution and explanation
8 more videos on this problem
3033. Modify the Matrix - LeetCode Weekly Contest 384 | Python, JavaScript, Java, C++CodingNinja · 4:06 · 589 views
3033 Modify the Matrix || Brute Force without extra space 🔥Ayush Rao · 3:06 · 369 views
3033. Modify the Matrix (Leetcode Easy)Programming Live with Larry · 3:16 · 336 views
3033. Modify The Matrix | Leetcode Contest 🚀💻✨"CodeRebel · 12:53 · 292 views
3033. Modify the Matrix || Leetcode Weekly Contest 384 || Optimal Solution 😎Code With Anubhav · 13:16 · 236 views
#LeetCode 3033 | Modify the Matrix #JavaSleepy Cracker · 5:27 · 175 views
3033. Modify the Matrix || Weekly Contest 384 || C++Priyanshi Porwal · 4:55 · 141 views
Modify the Matrix | LeetCode EASY | contestAbhishek Sharma · 8:11 · 134 views
leetcode 3033. Modify the MatrixAman Sharma · 3:07 · 52 views
The problem
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] <= 100- The input is generated such that each column contains at least one non-negative integer.
Approach overview
Problem 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 1: Single Pass Approach with Precomputed Column Maximums
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.
def modify_matrix(matrix):
m, n = len(matrix), len(matrix[0])
col_max = [-float('inf')] * n
for j in range(n):
for i in range(m):
col_max[j] = max(col_max[j], matrix[i][j])
for i in range(m):
for j in range(n):
if matrix[i][j] == -1:
matrix[i][j] = col_max[j]
return matrix
matrix = [[1, 2, -1], [4, -1, 6], [7, 8, 9]]
result = modify_matrix(matrix)
for row in result:
print(" ".join(map(str, row)))import java.util.Arrays;
public class ModifyMatrix {
public static int[][] modifyMatrix(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
int[] col_max = new int[n];
Arrays.fill(col_max, Integer.MIN_VALUE);
for (int j = 0; j < n; j++) {
for (int i = 0; i < m; i++) {
col_max[j] = Math.max(col_max[j], matrix[i][j]);
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == -1) {
matrix[i][j] = col_max[j];
}
}
}
return matrix;
}
public static void main(String[] args) {
int[][] matrix = {{1, 2, -1}, {4, -1, 6}, {7, 8, 9}};
int[][] result = modifyMatrix(matrix);
for (int[] row : result) {
for (int val : row) {
System.out.print(val + " ");
}
System.out.println();
}
}
}#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> modifyMatrix(vector<vector<int>> matrix) {
int m = matrix.size();
int n = matrix[0].size();
vector<int> col_max(n, INT_MIN);
for (int j = 0; j < n; j++) {
for (int i = 0; i < m; i++) {
col_max[j] = max(col_max[j], matrix[i][j]);
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == -1) {
matrix[i][j] = col_max[j];
}
}
}
return matrix;
}
int main() {
vector<vector<int>> matrix = {{1, 2, -1}, {4, -1, 6}, {7, 8, 9}};
vector<vector<int>> result = modifyMatrix(matrix);
for (const auto &row : result) {
for (int element : row) {
cout << element << " ";
}
cout << endl;
}
return 0;
}function modifyMatrix(matrix) {
const m = matrix.length;
const n = matrix[0].length;
const col_max = Array(n).fill(-Infinity);
for (let j = 0; j < n; j++) {
for (let i = 0; i < m; i++) {
if (matrix[i][j] > col_max[j]) {
col_max[j] = matrix[i][j];
}
}
}
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (matrix[i][j] === -1) {
matrix[i][j] = col_max[j];
}
}
}
return matrix;
}
const matrix = [
[1, 2, -1],
[4, -1, 6],
[7, 8, 9]
];
console.log(modifyMatrix(matrix));#include <stdio.h>
void modifyMatrix(int matrix[50][50], int m, int n) {
int col_max[50];
for (int j = 0; j < n; j++) {
col_max[j] = -1;
for (int i = 0; i < m; i++) {
if (matrix[i][j] > col_max[j]) {
col_max[j] = matrix[i][j];
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == -1) {
matrix[i][j] = col_max[j];
}
}
}
}
int main() {
int matrix[50][50] = {{1, 2, -1}, {4, -1, 6}, {7, 8, 9}};
int m = 3, n = 3;
modifyMatrix(matrix, m, n);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
printf("%d ", matrix[i][j]);
}
printf("\n");
}
return 0;
}using System;
class ModifyMatrixSolution {
public static int[,] ModifyMatrix(int[,] matrix) {
int m = matrix.GetLength(0);
int n = matrix.GetLength(1);
int[] colMax = new int[n];
for (int j = 0; j < n; j++) {
colMax[j] = Int32.MinValue;
for (int i = 0; i < m; i++) {
if (matrix[i, j] > colMax[j]) {
colMax[j] = matrix[i, j];
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i, j] == -1) {
matrix[i, j] = colMax[j];
}
}
}
return matrix;
}
static void Main(string[] args) {
int[,] matrix = { {1, 2, -1}, {4, -1, 6}, {7, 8, 9} };
int[,] result = ModifyMatrix(matrix);
for (int i = 0; i < result.GetLength(0); i++) {
for (int j = 0; j < result.GetLength(1); j++) {
Console.Write(result[i, j] + " ");
}
Console.WriteLine();
}
}
}In Python, we use a straightforward implementation where we iterate through each column to find the maximum, then replace -1 values in a subsequent pass.
Time Complexity: O(m * n).
Space Complexity: O(n).
Approach 2: Direct Replacement with Dynamic Maximum Finding
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.
def modify_matrix(matrix):
m, n = len(matrix), len(matrix[0])
for j in range(n):
col_max = max(matrix[i][j] for i in range(m) if matrix[i][j] != -1)
for i in range(m):
if matrix[i][j] == -1:
matrix[i][j] = col_max
return matrix
matrix = [[1, 2, -1], [4, -1, 6], [7, 8, 9]]
result = modify_matrix(matrix)
for row in result:
print(" ".join(map(str, row)))import java.util.Arrays;
public class ModifyMatrix {
public static int[][] modifyMatrix(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
for (int j = 0; j < n; j++) {
int colMax = Integer.MIN_VALUE;
for (int i = 0; i < m; i++) {
if (matrix[i][j] != -1) {
colMax = Math.max(colMax, matrix[i][j]);
}
}
for (int i = 0; i < m; i++) {
if (matrix[i][j] == -1) {
matrix[i][j] = colMax;
}
}
}
return matrix;
}
public static void main(String[] args) {
int[][] matrix = {{1, 2, -1}, {4, -1, 6}, {7, 8, 9}};
int[][] result = modifyMatrix(matrix);
for (int[] row : result) {
for (int val : row) {
System.out.print(val + " ");
}
System.out.println();
}
}
}function modifyMatrix(matrix) {
const m = matrix.length;
const n = matrix[0].length;
for (let j = 0; j < n; j++) {
let col_max = -Infinity;
for (let i = 0; i < m; i++) {
if (matrix[i][j] !== -1) {
col_max = Math.max(col_max, matrix[i][j]);
}
}
for (let i = 0; i < m; i++) {
if (matrix[i][j] === -1) {
matrix[i][j] = col_max;
}
}
}
return matrix;
}
const matrix = [[1, 2, -1], [4, -1, 6], [7, 8, 9]];
console.log(modifyMatrix(matrix));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.
Time Complexity: O(m2 * n), due to recalculating column maxima during each replacement.
Space Complexity: O(1), no additional space used beyond input matrix.
Approach 3: Simulation
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).
function modifiedMatrix(matrix: number[][]): number[][] {
const [m, n] = [matrix.length, matrix[0].length];
for (let j = 0; j < n; ++j) {
let mx = -1;
for (let i = 0; i < m; ++i) {
mx = Math.max(mx, matrix[i][j]);
}
for (let i = 0; i < m; ++i) {
if (matrix[i][j] === -1) {
matrix[i][j] = mx;
}
}
}
return matrix;
}func modifiedMatrix(matrix [][]int) [][]int {
m, n := len(matrix), len(matrix[0])
for j := 0; j < n; j++ {
mx := -1
for i := 0; i < m; i++ {
mx = max(mx, matrix[i][j])
}
for i := 0; i < m; i++ {
if matrix[i][j] == -1 {
matrix[i][j] = mx
}
}
}
return matrix
}Complexity comparison
| Approach | Complexity |
|---|---|
| Single Pass Approach with Precomputed Column Maximums | Time Complexity: O(m * n). |
| Direct Replacement with Dynamic Maximum Finding | Time Complexity: O(m2 * n), due to recalculating column maxima during each replacement. |
| Simulation | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Modify the Matrix easy or hard?
Modify the Matrix is considered an Easy problem on LeetCode with an acceptance rate around 69%. The challenge mainly checks whether you recognize redundant computation and optimize it by precomputing column maximum values.
Modify the Matrix Python/Java solution
Python and Java implementations follow the same logic: compute column maximums using a loop over rows and columns, store them in an array, then iterate again to replace -1 cells. This keeps the solution O(m * n) and easy to implement in most languages.
How to solve Modify the Matrix in O(n)?
Treat n as the number of columns and compute a column maximum array in one pass over the matrix. Store the maximum value seen in each column, then run a second pass to replace every -1 with that column’s maximum. The total complexity becomes O(m * n) with O(n) additional space.
What is the best approach for Modify the Matrix?
The best approach is to precompute the maximum value for each column, then replace every -1 with that stored maximum. This avoids repeatedly scanning the same column. The algorithm runs in O(m * n) time with O(n) extra space, where m is the number of rows and n is the number of columns.
Is Modify the Matrix asked at Google/Amazon/Meta?
Problems involving matrix traversal and column aggregation are common in interviews at companies like Amazon, Google, and Meta. While this exact LeetCode problem may not appear verbatim, the pattern of preprocessing column or row statistics frequently appears in interview questions.
What data structure is used in Modify the Matrix?
The solution primarily uses a 2D array (matrix). The optimal implementation also uses a 1D array to store the maximum value for each column, allowing constant-time replacement of -1 cells.
What is the time complexity of Modify the Matrix?
The optimal solution runs in O(m * n) time because the matrix is scanned twice: once to compute column maximums and once to replace -1 values. A naive approach that recomputes the column maximum for every -1 can degrade to about O(m^2 * n) time.