Modify the Matrix — Editorial

Opening the reading…

Intuitionwhy each missing value needs a column summary

A -1 does not depend on its row or on neighboring cells. Its replacement is determined only by the other values in the same column, so each column can be summarized by one number: its maximum. Once that summary is known, every -1 in the column receives exactly the same value, while every non-negative cell stays unchanged.

The safest order is therefore two separate passes. First inspect the original matrix and compute all column maxima. Then copy the matrix and make replacements in the copy. Keeping these jobs separate matters because a -1 near the top of a column must wait for a larger non-negative value that may appear much lower in that column.

Approach

Read m and n from the matrix and create colMax with one slot per column, because each replacement needs a stored answer for its column.

For every column j, scan all rows i and keep the largest matrix[i][j], because looking at the complete original column is what guarantees that no later value is missed.

Copy matrix into answer before changing anything, because the required result preserves every non-negative cell and leaves the input available as the untouched source.

Scan every cell of answer and test whether it equals -1, because only missing cells may be changed and existing values must pass through unchanged.

Replace answer[i][j] with colMax[j] when the cell is -1, because the column index selects the maximum that defines this replacement.

Return answer after all cells have been processed, because returning earlier could leave some -1 values unreplaced.

Complexitythe two full scans are still linear in the matrix size

MEASURE	BOUND	WHY
Time	O(m x n)	The maximum pass examines each of the m x n input cells once, and the replacement pass examines each answer cell once. Copying the matrix also touches each cell once, so the constant number of full traversals remains O(m x n).
Space	O(n) extra	colMax stores one value per column. The returned answer matrix uses O(m x n) storage, but it is required output and is excluded from the extra-space bound. The extra space remains O(n) for every allowed matrix shape; the output itself is O(m x n).

Here m is the number of rows and n is the number of columns.

Annotated solutionC++ · two passes with a copied answer matrix

CPPCompute every column maximum, copy the matrix, and replace only its -1 cells.

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> modifiedMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();

        vector<int> colMax(n, -1);
        for (int j = 0; j < n; ++j) {
            int mx = -1;
            for (int i = 0; i < m; ++i) {
                mx = max(mx, matrix[i][j]);
            }
            colMax[j] = mx;
        }

        vector<vector<int>> answer = matrix;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (answer[i][j] == -1) {
                    answer[i][j] = colMax[j];
                }
            }
        }

        return answer;
    }
};

The initialization colMax[j] = -1 is safe because every matrix value is at least -1, and each column is guaranteed to contain a non-negative value. The important placement is the copy before replacement: answer is the object being edited, while matrix remains the original source used to compute the correct column summaries.