Modify the Matrix

Easy
1003.

Modify the Matrix

Modify the Matrix is an easy coding problem on arrays and matrix, asked in Amazon, Google and Capgemini interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} matrix
 * @return {number[][]}
 */
var modifiedMatrix = function(matrix) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Modify the Matrix — Solution in Python, Java & C++

Modify the Matrix solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem on arrays and matrix.

Modify the Matrix is an easy coding problem on arrays and matrix, asked in Amazon, Google and Capgemini interviews.

  • Difficulty: Easy
  • Topics: Arrays, Matrix
  • Asked at: Amazon, Google, Capgemini
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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.

Hints for Modify the Matrix

  1. Hint 1

    Compute each column's maximum before replacing anything.

  2. Hint 2

    A -1 is never the maximum, so it can be included in the scan harmlessly.

  3. Hint 3

    Build a new matrix rather than modifying in place.

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

Java

public static int[][] modifiedMatrix(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    int[] colMax = new int[n];
    Arrays.fill(colMax, -1);
    for (int j = 0; j < n; j++) {
        for (int i = 0; i < m; i++) colMax[j] = Math.max(colMax[j], matrix[i][j]);
    }
    int[][] out = new int[m][n];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) out[i][j] = matrix[i][j] == -1 ? colMax[j] : matrix[i][j];
    }
    return out;
}

C++

vector<vector<int>> modifiedMatrix(vector<vector<int>>& matrix) {
    int m = (int) matrix.size(), n = (int) matrix[0].size();
    vector<int> colMax(n, -1);
    for (int j = 0; j < n; j++) {
        for (int i = 0; i < m; i++) colMax[j] = max(colMax[j], matrix[i][j]);
    }
    vector<vector<int>> out(m, vector<int>(n));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) out[i][j] = matrix[i][j] == -1 ? colMax[j] : matrix[i][j];
    }
    return out;
}

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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Matrix and Grid Traversal