Skip to main content
Talentd

Modify the Matrix - Solution & Explanation

EasyArrayMatrix14 min readAsked at: Fidelity
Practice this problem

Problem Statement

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.

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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

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.

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.

Code

PythonJavaJavaScript

Python

Java

JavaScript

Complexity

Time Complexity: O(m2 * n), due to recalculating column maxima during each replacement.
Space Complexity: O(1), no additional space used beyond input matrix.

Try this approach in the editor →

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).

Code

PythonJavaC++GoTypeScriptC#

Python

Java

C++

Go

TypeScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(n), where n is the number of columns, due to the extra space for storing column maximums.

Direct Replacement with Dynamic Maximum Finding

Time Complexity: O(m2 * n), due to recalculating column maxima during each replacement.
Space Complexity: O(1), no additional space used beyond input matrix.

Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Direct Replacement with Dynamic Maximum FindingO(m^2 * n)O(1)Useful for understanding the problem or when avoiding extra memory is required
Single Pass with Precomputed Column MaximumsO(m * n)O(n)Best general solution; avoids repeated column scans and is optimal for interviews

Video Solution

3033. Modify the Matrix - LeetCode Weekly Contest 384 | Python, JavaScript, Java, C++ • CodingNinja • 589 views views

Watch 8 more video solutions →

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.

Ready to solve this problem?

Practice Modify the Matrix with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays