Scale Engineer

Modify the Matrix

Easy
#2701Time: O(m^2 * n). The nested loops iterate through `m * n` cells. For each cell containing `-1`, we perform a column scan taking `O(m)` time. In the worst case, where a large fraction of cells are `-1`, the complexity is `O(m * n * m)`.Space: O(m * n). A new matrix `answer` of the same dimensions as the input is created, requiring space proportional to the number of elements.1 company
Data structures
ArrayMatrix
Companies
Fidelity

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly translates the problem statement into code. It involves creating a copy of the input matrix and then iterating through each cell of this new matrix. Whenever a cell with a value of -1 is found, a separate search is initiated within its corresponding column to find the maximum value. This maximum value then replaces the -1.

Algorithm

  1. Get the dimensions of the matrix, m (rows) and n (columns).
  2. Create a new m x n matrix, answer, as a deep copy of the input matrix.
  3. Iterate through each cell (i, j) of the answer matrix.
  4. If answer[i][j] is -1: a. Initialize a variable maxInCol to a very small number (e.g., -1, since all other numbers are non-negative). b. Initiate a new loop to scan the entire column j of the original matrix (from row k = 0 to m-1). c. In this inner loop, update maxInCol by comparing it with matrix[k][j]. d. After the column scan is complete, update the cell in the new matrix: answer[i][j] = maxInCol.
  5. After iterating through all cells, return the answer matrix.

Walkthrough

The algorithm begins by creating an exact copy of the input matrix, let's call it answer. It then uses nested loops to traverse every element of answer. For each element, it checks if its value is -1. If it is, the algorithm performs another full scan of that element's column in the original matrix to find the maximum value. This maximum value is then used to replace the -1 in the answer matrix. This process is repeated for all elements. Using the original matrix for finding the maximum is crucial to avoid using a value that was just replaced in the same column's calculation.

class Solution {    public int[][] modifiedMatrix(int[][] matrix) {        int m = matrix.length;        int n = matrix[0].length;        int[][] answer = new int[m][n];         // Create a copy of the matrix        for (int i = 0; i < m; i++) {            for (int j = 0; j < n; j++) {                answer[i][j] = matrix[i][j];            }        }         // Iterate and replace -1s        for (int i = 0; i < m; i++) {            for (int j = 0; j < n; j++) {                if (answer[i][j] == -1) {                    int maxInCol = -1;                    // Find the maximum in the current column from the original matrix                    for (int k = 0; k < m; k++) {                        maxInCol = Math.max(maxInCol, matrix[k][j]);                    }                    answer[i][j] = maxInCol;                }            }        }        return answer;    }}

Complexity

Time

O(m^2 * n). The nested loops iterate through `m * n` cells. For each cell containing `-1`, we perform a column scan taking `O(m)` time. In the worst case, where a large fraction of cells are `-1`, the complexity is `O(m * n * m)`.

Space

O(m * n). A new matrix `answer` of the same dimensions as the input is created, requiring space proportional to the number of elements.

Trade-offs

Pros

  • Simple to understand and implement as it directly follows the problem's logic.

Cons

  • Highly inefficient due to redundant computations. The maximum of a column is recalculated for every -1 found in that column, leading to a poor time complexity.

Solutions

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;    }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem