# Modify the Matrix
**Difficulty:** EASY
[External](https://leetcode.com/problems/modify-the-matrix)
Canonical: https://scaleengineer.com/dsa/problems/modify-the-matrix
**Data structures:** Array, Matrix
**Companies:** [Fidelity](https://scaleengineer.com/companies/fidelity)
---
## Problem
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:**

![](https://assets.glich.co/dsa/modify-the-matrix/image0.png) 

**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:**

![](https://assets.glich.co/dsa/modify-the-matrix/image1.png) 

**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
## Brute-Force with Repeated Column Scan
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`.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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.

## Two-Pass Approach with Pre-computation
This is a more efficient approach that avoids the redundant calculations of the brute-force method. It works in two main phases. In the first pass, we iterate through the matrix once to determine the maximum value for each column and store these maximums in an auxiliary array. In the second pass, we build the result matrix, using the pre-computed maximums from the auxiliary array to replace any `-1` values.
**Time:** O(m * n). The first pass to find all column maximums takes `O(m * n)`. The second pass to construct the `answer` matrix also takes `O(m * n)`. The total time complexity is `O(m * n) + O(m * n)`, which simplifies to `O(m * n)`. · **Space:** O(m * n). We use `O(n)` extra space for the `colMaxs` array and `O(m * n)` space for the `answer` matrix. The space for the `answer` matrix is the dominant factor.
**Pros:** Significantly more efficient than the brute-force approach, with a linear time complexity relative to the matrix size.; Avoids redundant work by pre-calculating column maximums.
**Cons:** Requires a small amount of extra space (`O(n)`) for the auxiliary array to store column maximums.; Requires two separate passes over the matrix data.
### Explanation
The core idea is to pre-compute the maximum value for each column before attempting to modify the matrix. We start by creating an array, `colMaxs`, to hold these maximums. We then perform a full scan of the input matrix, column by column, to populate this `colMaxs` array. Once we have the maximum for every column, we create the new `answer` matrix. We then perform a second scan of the input matrix. During this scan, we populate the `answer` matrix: if an element in the input is `-1`, we fill the corresponding cell in `answer` with the pre-computed max from `colMaxs`; otherwise, we just copy the element's value. This eliminates the need to re-scan columns repeatedly.

```java
class Solution {
    public int[][] modifiedMatrix(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;

        // Step 1: Find the maximum of each column
        int[] colMaxs = new int[n];
        for (int j = 0; j < n; j++) {
            int maxVal = -1;
            for (int i = 0; i < m; i++) {
                maxVal = Math.max(maxVal, matrix[i][j]);
            }
            colMaxs[j] = maxVal;
        }

        // Step 2: Create the answer matrix and fill it based on the pre-computed maxes
        int[][] answer = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == -1) {
                    answer[i][j] = colMaxs[j];
                } else {
                    answer[i][j] = matrix[i][j];
                }
            }
        }

        return answer;
    }
}
```
### Algorithm
1. Get the matrix dimensions, `m` (rows) and `n` (columns).
2. Create a 1D auxiliary array, `colMaxs`, of size `n`.
3. **First Pass:** Iterate through each column `j` from `0` to `n-1`.
    a. For each column, find its maximum value by iterating through all its rows (`i` from `0` to `m-1`).
    b. Store the computed maximum in `colMaxs[j]`.
4. Create the final `answer` matrix of size `m x n`.
5. **Second Pass:** Iterate through the original `matrix` from `(0,0)` to `(m-1, n-1)`.
    a. For each cell `(i, j)`, check if `matrix[i][j]` is `-1`.
    b. If it is, set `answer[i][j] = colMaxs[j]`.
    c. Otherwise, copy the value: `answer[i][j] = matrix[i][j]`.
6. Return the `answer` matrix.

# Solutions
### CSharp

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

### Java

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

```

### CPP

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

```

### Python

```python
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

```