Question

3033. Modify the Matrix

中文文档

Description

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.

Solutions

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.

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

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

class Solution {
  public int[][] modifiedMatrix(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    for (int j = 0; j < n; ++j) {
      int mx = -1;
      for (int i = 0; i < m; ++i) {
        mx = Math.max(mx, matrix[i][j]);
      }
      for (int i = 0; i < m; ++i) {
        if (matrix[i][j] == -1) {
          matrix[i][j] = mx;
        }
      }
    }
    return matrix;
  }
}

class Solution {
public:
  vector<vector<int>> modifiedMatrix(vector<vector<int>>& matrix) {
    int m = matrix.size(), n = matrix[0].size();
    for (int j = 0; j < n; ++j) {
      int mx = -1;
      for (int i = 0; i < m; ++i) {
        mx = max(mx, matrix[i][j]);
      }
      for (int i = 0; i < m; ++i) {
        if (matrix[i][j] == -1) {
          matrix[i][j] = mx;
        }
      }
    }
    return matrix;
  }
};

func modifiedMatrix(matrix [][]int) [][]int {
  m, n := len(matrix), len(matrix[0])
  for j := 0; j < n; j++ {
    mx := -1
    for i := 0; i < m; i++ {
      mx = max(mx, matrix[i][j])
    }
    for i := 0; i < m; i++ {
      if matrix[i][j] == -1 {
        matrix[i][j] = mx
      }
    }
  }
  return matrix
}

function modifiedMatrix(matrix: number[][]): number[][] {
  const [m, n] = [matrix.length, matrix[0].length];
  for (let j = 0; j < n; ++j) {
    let mx = -1;
    for (let i = 0; i < m; ++i) {
      mx = Math.max(mx, matrix[i][j]);
    }
    for (let i = 0; i < m; ++i) {
      if (matrix[i][j] === -1) {
        matrix[i][j] = mx;
      }
    }
  }
  return matrix;
}

public class Solution {
  public int[][] ModifiedMatrix(int[][] matrix) {
    int m = matrix.Length, n = matrix[0].Length;
    for (int j = 0; j < n; ++j) {
      int mx = -1;
      for (int i = 0; i < m; ++i) {
        mx = Math.Max(mx, matrix[i][j]);
      }
      for (int i = 0; i < m; ++i) {
        if (matrix[i][j] == -1) {
          matrix[i][j] = mx;
        }
      }
    }
    return matrix;
  }
}