73. Set Matrix Zeroes
Set Matrix Zeroes
Given an m x n
integer matrix matrix
, if an element is 0
, set its entire row and column to 0
's.
You must do it in place.
Example 1:
Input: matrix = [[1,1,1],[1,0,1],[1,1,1]] Output: [[1,0,1],[0,0,0],[1,0,1]]
Example 2:
Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]] Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]
Constraints:
m == matrix.length
n == matrix[0].length
1 <= m, n <= 200
-231 <= matrix[i][j] <= 231 - 1
Follow up:
- 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?
var setZeroes = function(matrix) {
let isCol = false, r = matrix.length, c = matrix[0].length;
for (let i = 0; i < r; i++) {
if (!matrix[i][0]) isCol = true;
for (let j = 1; j < c; j++) {
if (!matrix[i][j]) {
matrix[i][0] = 0;
matrix[0][j] = 0;
};
}
}
for (let i = 1; i < r; i++) {
for (let j = 1; j < c; j++) {
if (!matrix[i][0] || !matrix[0][j]) matrix[i][j] = 0;
}
}
if (!matrix[0][0]) {
for (let j = 0; j < c; j++) matrix[0][j] = 0;
}
if (isCol) {
for (let i = 0; i < r; i++) {
matrix[i][0] = 0;
}
}
};
var setZeroes = function(matrix) {
const rowSet = new Set(), colSet = new Set()
for (let i = 0; i < matrix.length; i++) {
for (let j = 0; j < matrix[i].length; j++) {
if (!matrix[i][j]) {
rowSet.add(i);
colSet.add(j);
};
}
}
for (let i = 0; i < matrix.length; i++) {
for (let j = 0; j < matrix[i].length; j++) {
if (rowSet.has(i) || colSet.has(j)) matrix[i][j] = 0
}
}
};
var setZeroes = function(matrix) {
const copy = JSON.parse(JSON.stringify(matrix));
for (let i = 0; i < matrix.length; i++) {
for (let j = 0; j < matrix[i].length; j++) {
if (!copy[i][j]) traverse(i, j);
}
}
function traverse(row, col, dir = 'all') {
matrix[row][col] = 0;
if (row - 1 >= 0 && (dir === 'all' || dir === 'up')) traverse(row - 1, col, 'up');
if (row + 1 <= matrix.length - 1 && (dir === 'all' || dir === 'down')) traverse(row + 1, col, 'down');
if (col - 1 >= 0 && (dir === 'all' || dir === 'left')) traverse(row, col - 1, 'left');
if (col + 1 <= matrix[row].length - 1 && (dir === 'all' || dir === 'right')) traverse(row, col + 1, 'right');
}
};
That’s all folks! In this post, we solved LeetCode problem 73. Set Matrix Zeroes
I hope you have enjoyed this post. Feel free to share your thoughts on this.
You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.
In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!
Comments
Post a Comment