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.

Description Solution Video 4:06

3033. Modify the Matrix

Easy69.1% acceptance1 company

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.

Asked at 1 company

Fidelity

Topics

Array Matrix

4:06

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def modifiedMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[[1,2,-1],[4,-1,6],[7,8,9]]

Input

[[3,-1],[5,2]]

Your code is saved on this device.Solution