A straightforward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?
Solutions
Solution 1: Array Mark
We use arrays rows and cols to mark the rows and columns to be cleared.
Then traverse the matrix again, and clear the elements in the rows and columns marked in rows and cols.
The time complexity is $O(m\times n)$, and the space complexity is $O(m+n)$. Where $m$ and $n$ are the number of rows and columns of the matrix respectively.
/** Do not return anything, modify matrix in-place instead. */functionsetZeroes(matrix:number[][]):void{constm=matrix.length;constn=matrix[0].length;constrows:boolean[]=newArray(m).fill(false);constcols:boolean[]=newArray(n).fill(false);for(leti=0;i<m;++i){for(letj=0;j<n;++j){if(matrix[i][j]===0){rows[i]=true;cols[j]=true;}}}for(leti=0;i<m;++i){for(letj=0;j<n;++j){if(rows[i]||cols[j]){matrix[i][j]=0;}}}}
1 2 3 4 5 6 7 8 910111213141516171819202122232425
/** * @param {number[][]} matrix * @return {void} Do not return anything, modify matrix in-place instead. */varsetZeroes=function(matrix){constm=matrix.length;constn=matrix[0].length;constrows=newArray(m).fill(false);constcols=newArray(n).fill(false);for(leti=0;i<m;++i){for(letj=0;j<n;++j){if(matrix[i][j]==0){rows[i]=true;cols[j]=true;}}}for(leti=0;i<m;++i){for(letj=0;j<n;++j){if(rows[i]||cols[j]){matrix[i][j]=0;}}}};
In the first method, we use an additional array to mark the rows and columns to be cleared. In fact, we can also use the first row and first column of the matrix to mark them, without creating an additional array.
Since the first row and the first column are used to mark, their values may change due to the mark, so we need additional variables $i0$, $j0$ to mark whether the first row and the first column need to be cleared.
The time complexity is $O(m\times n)$, and the space complexity is $O(1)$. Where $m$ and $n$ are the number of rows and columns of the matrix respectively.
/** Do not return anything, modify matrix in-place instead. */functionsetZeroes(matrix:number[][]):void{constm=matrix.length;constn=matrix[0].length;consti0=matrix[0].includes(0);constj0=matrix.map(row=>row[0]).includes(0);for(leti=1;i<m;++i){for(letj=1;j<n;++j){if(matrix[i][j]===0){matrix[i][0]=0;matrix[0][j]=0;}}}for(leti=1;i<m;++i){for(letj=1;j<n;++j){if(matrix[i][0]===0||matrix[0][j]===0){matrix[i][j]=0;}}}if(i0){matrix[0].fill(0);}if(j0){for(leti=0;i<m;++i){matrix[i][0]=0;}}}