Modify the Matrix — Easy Problem & Solution

Problem statement

Replace every -1 in the matrix with the largest value in its own column, and return the result. The original matrix is not changed.

Example 1

Input: matrix = [[1,2,-1],[4,-1,6],[7,8,9]]
Output: [[1,2,9],[4,8,6],[7,8,9]]
Explanation: Column 2's maximum is 9 and column 1's is 8.

Example 2

Input: matrix = [[3,-1],[5,2]]
Output: [[3,2],[5,2]]

Example 3

Input: matrix = [[1,2],[3,4]]
Output: [[1,2],[3,4]]
Explanation: Nothing to replace.

Constraints

• m == matrix.length
• n == matrix[i].length
• 2 <= m, n <= 50
• -1 <= matrix[i][j] <= 100
• The input is generated so that each column contains at least one non-negative integer.

How to solve Modify the Matrix

Two passes: find each column's maximum, then build the answer, substituting the column maximum wherever a -1 sits.

Approach

1. For each column, scan down and record the largest value.
2. Build the result, replacing -1 with its column's maximum.

Why it works

The maxima must all be computed before any substitution: replacing in place would let a freshly written value become the maximum of a later column scan. Including the -1s in the max scan is harmless, since every column is promised at least one non-negative entry.

Complexity

• Time — O(m · n)
• Space — O(m · n) for the output

Pitfalls

• Replacing in place while still computing maxima corrupts later columns.
• The maximum is per column, not per row or over the whole matrix.
• Start the running maximum at -1, not 0, since values may be 0.

Reference solution

Python

from typing import List

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

JavaScript

var modifiedMatrix = function(matrix) {
    var m = matrix.length, n = matrix[0].length, i, j;
    var colMax = [];
    for (j = 0; j < n; j++) colMax.push(-1);
    for (j = 0; j < n; j++) {
        for (i = 0; i < m; i++) if (matrix[i][j] > colMax[j]) colMax[j] = matrix[i][j];
    }
    var out = [];
    for (i = 0; i < m; i++) {
        var row = [];
        for (j = 0; j < n; j++) row.push(matrix[i][j] === -1 ? colMax[j] : matrix[i][j]);
        out.push(row);
    }
    return out;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Special Array I Easy
• Type of Triangle Easy
• Find the Losers of the Circular Game Easy
• Form Smallest Number From Two Digit Arrays Easy
• Delete Greatest Value in Each Row Easy
• The Employee That Worked on the Longest Task Easy