#3033

Easy

LeetCode Problem Workspace

Modify the Matrix

Modify the Matrix efficiently by replacing all -1 elements with the maximum in their column using array and matrix operations.

array matrix

Problem Statement

Given a 0-indexed m x n integer matrix, create a new matrix called answer. Copy all values from matrix to answer, then for every element equal to -1, replace it with the maximum value found in its column.

Return the updated answer matrix. For example, given matrix = [[1,2,-1],[4,-1,6],[7,8,9]], the resulting answer should be [[1,2,9],[4,8,6],[7,8,9]]. Each column is guaranteed to have at least one non-negative integer.

Examples

Example 1

Input: matrix = [[1,2,-1],[4,-1,6],[7,8,9]]

Output: [[1,2,9],[4,8,6],[7,8,9]]

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]]

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.

Solution Approach

Column Maximum Preprocessing

First, traverse each column to find the maximum value ignoring -1. Store these maxima in an array, allowing O(1) access when replacing -1 values during the next pass through the matrix.

Matrix Update Pass

Iterate through the matrix again. For each cell with value -1, replace it with the precomputed column maximum. All other values remain unchanged. This ensures a single predictable replacement per -1.

Time and Space Optimization

Use an array of size n for column maxima to minimize extra space. Overall time complexity is O(m*n) with O(n) extra space, avoiding repeated scans for each -1 and keeping the solution efficient for up to 50x50 matrices.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(m*n) due to two full passes through the matrix. Space complexity is O(n) to store the maximum for each column.

What Interviewers Usually Probe

Can you precompute any values to avoid multiple scans of the matrix?
How would you handle matrices where multiple -1s appear in the same column?
Is there a way to do this without modifying the original matrix in place?

Common Pitfalls or Variants

Common pitfalls

Scanning each -1 individually for its column maximum increases runtime unnecessarily.
Modifying the original matrix before storing column maxima can overwrite needed data.
Assuming every column may have only one -1 can lead to incorrect replacements.

Follow-up variants

Replace -1 with the minimum value in its row instead of column maxima.
Handle larger matrices where -1 can appear in multiple columns simultaneously.
Allow negative numbers to be valid maxima and adjust replacement logic accordingly.

FAQ

What is the best way to replace -1 values in Modify the Matrix?

Compute the maximum of each column first, then replace -1 values in one pass using these precomputed maxima.

Does this problem require modifying the original matrix?

No, creating a separate answer matrix preserves the original while allowing safe replacements.

What is the time complexity for replacing all -1s in the matrix?

It is O(m*n) because each cell is visited twice: once for maxima and once for replacements.

Can the solution handle matrices with multiple -1s in the same column?

Yes, since the column maxima are precomputed, all -1s in a column are replaced correctly in a single pass.

Which pattern does this problem exemplify?

This is an Array plus Matrix pattern, focusing on column-wise computation and replacement logic.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

class Solution:
    def modifiedMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
        m, n = len(matrix), len(matrix[0])
        for j in range(n):
            mx = max(matrix[i][j] for i in range(m))
            for i in range(m):
                if matrix[i][j] == -1:
                    matrix[i][j] = mx
        return matrix

Continue Practicing

#3030 find the grid of region average #3044 most frequent prime #3070 count submatrices with top left element and sum less than k